game 题解

很板的最短路。

一眼看上去，我们要跑 $n$ 次 dij，求出每个国家相互之间的最短距离，时间复杂度 $O(nm\log n)$。

但其实并不用。

考虑建虚点。我们将每个国家向虚点建一个权值为售价的单向边，然后求各个国家与虚点的最短路即可。

但是这样还是 $O(nm\log n)$ 啊……是吗？

注意到我们可以反向连边，则虚点到某个国家的最短路就是它到虚点的最短路。这样只需要跑一次 dij 即可。

#include <iostream>
#include <cstdio>
#include <queue>
#include <vector>
#include <memory.h>
#define int long long
#define pii pair <int, int>
using namespace std;
vector <pii> v[200005];
int a[200005];
int dis[200005];
bool vis[200005];
int n, m;
priority_queue <pii, vector <pii>, greater <pii>> q;
signed main(){
    freopen("game.in", "r", stdin);
    freopen("game.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	for(int i = 1; i <= m; i++){
		int x, y, z;
		cin >> x >> y >> z;
		v[x].push_back({y, z * 2});
		v[y].push_back({x, z * 2});
	}
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		v[n + 1].push_back({i, a[i]});
	}
	memset(dis, 63, sizeof(dis));
	q.push({0, n + 1});
	dis[n + 1] = 0;
	while(!q.empty()){
		auto head = q.top();
		q.pop();
		if(vis[head.second]) continue;
		vis[head.second] = 1;
		for(auto i:v[head.second]){
			if(dis[i.first] > head.first + i.second){
				dis[i.first] = head.first + i.second;
				q.push({dis[i.first], i.first});
			}
		}
	}
	for(int i = 1; i <= n; i++){
		cout << dis[i] << ' ';
	}
    cout.flush();
    fclose(stdin), fclose(stdout);

	return 0;
}

时间复杂度：$O(m\log n)$。