小Biu看电影

【题目描述】
无聊的小Biu来到了电影之城，他发现这里有 (n) 个电影院，而且每个电影院的电影票价是不同的，有一些电影院之间有双向联通的道路，想要通过某条道路需要一定的花费，小Biu想知道，他以每一个电影院为起点(当然也可以原地不动)，最少需要多少花费可以看到电影。

【输入格式】
第 1 行：两个整数 (n,m)，(n) 表示城市中电影院的个数，(m) 表示电影院之间的道路总数。((1leq nleq 100000,1leq mleq 300000))
第 2 行：(n) 个正整数，第 (i) 个正整数表示在第 (i) 个电影院看电影的票价 (val[i])。((1leq val[i]leq 1000))
第 3~m+2 行：每行三个正整数,(u,v,w),表示电影院 (u) 与电影院 (v) 之间有一条花费为 (w) 的道路。((1leq u,vleq n,1leq wleq 1000))

【输出格式】
输出 (n) 行每行一个正整数。
第 (i) 行输出的正整数表示从第 (i) 个电影院出发，最少需要多少花费可以看到电影。

看上去好像蜃难
其实似乎也挺简单

把 从一个电影院出发走到任意一个电影院看电影 倒过来 理解成 在任意一个电影院看完电影然后回到指定电影院
然后就可以想到建立一个虚点 将虚点与每个电影院之间连一条权为(val[i])(即票价)的边 然后从(i)影院出发看到电影的最小代价实际上就是虚点到(i)的最短路
然后跑一遍Dijkstra就行了

#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;
typedef long long ll;

ll read() {
	ll ret = 0, flag = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0') {
		if (ch == '-') flag = -1;
		ch = getchar();
	}
	while (ch <= '9' && ch >= '0') {
		ret = (ret << 3) + (ret << 1) + (ch ^ '0');
		ch = getchar();
	}
	return ret * flag;
}

ll n, m, val[1000005], ans;
ll head[1000005], pre[1000005], to[1000005], dis[1000005], sz;
ll dist[1000005];
bool vis[100005];

void insert(ll u, ll v, ll w) {
	to[++sz] = v; dis[sz] = w; pre[sz] = head[u]; head[u] = sz;
}

void dijkstra(ll st) {
	priority_queue< pair<ll, ll> , vector< pair<ll, ll> > , greater< pair<ll, ll> > > q;
	q.push(make_pair(0, st));
	while (!q.empty()) {
		ll x = q.top().second;
		q.pop();
		if (vis[x]) continue;
		else vis[x] = 1;
		for (int i = head[x]; i; i = pre[i]) {
			ll y = to[i];
			if (dist[y] > dist[x] + dis[i]) {
				dist[y] = dist[x] + dis[i];
				q.push(make_pair(dist[y], y));
			}
		}
	}
}

int main() {
	n = read(); m = read();
	for (int i = 1; i <= n; i++) {
		val[i] = read();
		insert(0, i, val[i]);
	}
	for (int i = 1; i <= m; i++) {
		ll u, v, w;
		u = read(); v = read(); w = read();
		insert(u, v, w * 2);
		insert(v, u, w * 2);
	}
	ans = 0x7fffffff;
	for (int j = 1; j <= n; j++) {
		dist[j] = 0x7fffffff;
		vis[j] = 0;
	}
	dist[0] = 0;
	dijkstra(0);
	for (int i = 1; i <= n; i++) printf("%lld
", dist[i]);
	return 0;
}