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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#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\n", dist[i]);
return 0;
}

评论