DragonBallII

The first line of input contains three space-separated integers n, m, and k (1 ≤ n, k ≤ 1 000, 1 ≤ m ≤ 10 000), thenumber of cities, teleport trips, and Dragon Balls, respectively. Then follow m lines containing three space-separatedintegers a_i , b_i , and ti each (1 ≤ a_i , b_i≤ n, 0 ≤ t_i ≤ 10 000), which, as explained above, represent the two citiesconnected by the teleport trip, and cost to use the teleporter.Then follow k lines, the i-th of which contains two space-separated integers c_i and d_i (1 ≤ c_i , d_i≤ n), indicatingthat the i-th Dragon Ball is located in city c_i and has serial number d_i . Note that there might be multiple Dragon Ballslocated in the same city, multiple Dragon Balls that share the same serial number, or even multiple Dragon Balls withthe same serial number in the same city.

C++ 解法, 执行用时: 1611ms, 内存消耗: 16168K, 提交时间: 2021-08-19 16:38:48

#include <cstdio>
#include <queue>
#include <vector>
#include <random>
#include <algorithm>
#define pb push_back
#define INF 0x3f3f3f3f
using std::queue;
using std::vector;
const int N=200005;
std::mt19937 rnd(114);
int n, m, k, p[8], T=800;
int ans, cur;
vector<int> e[N], w[N], id[N];
int rid[8];
int q[N<<5], *ql, *qr;
//queue<int> q;
int in[N], ok[N][8];
int dis[1<<7][N], *rdis;
inline void ins(int u)
{
	if(rdis[u]<rdis[*ql]) *(--ql)=u;
	else *(++qr)=u;
}
void dij(int *dis)
{
	std::fill(in+1, in+n+1, 1);
	rdis=dis;
	ql=q+16*n, qr=ql-1;
	for(int i=1; i<=n; ++i) ins(i);
	while(ql<=qr)
	{
		int u=*(ql++);
		in[u]=0;
		if(dis[u]>=ans) continue;
		for(int i=0; i<e[u].size(); ++i)
		{
			int v=e[u][i], c=w[u][i];
			if(dis[v]>dis[u]+c)
			{
				dis[v]=dis[u]+c;
				if(!in[v]) ins(v);
			}
		}
	}
}
void solve(void)
{
	std::iota(p, p+8, 0);
	for(int i=1; i<=7; ++i) rid[i]=0;
	for(int i=1; i<=n; ++i) std::fill(ok[i], ok[i]+8, 0);
	for(int i=1; i<=n; ++i)
	{
		int t=rnd()%7;
		rid[t]=1;
//		t=i-1;
		for(int x:id[i]) ok[x][t]=1;
	}
//	for(int i=0; i<7; ++i) if(!rid[i]) return;
	for(int s=0; s<(1<<7); ++s) std::fill(dis[s], dis[s]+n+1, INF);
	dis[0][1]=0;
	for(int s=0; s<(1<<7); ++s)
	{
		for(int u=1; u<=n; ++u) for(int i=0; i<7; ++i) if((s&(1<<i))&&ok[u][i])
		{
			dis[s][u]=std::min(dis[s][u], dis[s^(1<<i)][u]);
		}
		dij(dis[s]);
	}
	for(int i=1; i<=n; ++i) ans=std::min(ans, dis[(1<<7)-1][i]);
}
int main()
{
	scanf("%d%d%d", &n, &m, &k);
	for(int i=1, x, y, z; i<=m; ++i) scanf("%d%d%d", &x, &y, &z), e[x].pb(y), w[x].pb(z), e[y].pb(x), w[y].pb(z);
	for(int i=1, c, d; i<=k; ++i) scanf("%d%d", &c, &d), id[d].pb(c);
	ans=INF;
	while(T--) solve();
	printf("%d\n", ans==INF?-1:ans);
	return 0;
}

详情