You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
58 lines
1.3 KiB
58 lines
1.3 KiB
#include <bits/stdc++.h>
|
|
|
|
using namespace std;
|
|
typedef pair<int, int> PII;
|
|
struct Node {
|
|
int var, next, val;
|
|
} edge[100000005];
|
|
int head[100005], tot, dis[100005], N, M;
|
|
bool vis[100005];
|
|
priority_queue<PII> Q;
|
|
|
|
void add(int a, int b, int c) {
|
|
edge[++tot].var = b;
|
|
edge[tot].val = c;
|
|
edge[tot].next = head[a];
|
|
head[a] = tot;
|
|
}
|
|
|
|
void init()//多组输入调用
|
|
{
|
|
tot = 0;
|
|
memset(head, 0, sizeof(head));
|
|
}
|
|
|
|
void dijkstra(int s) {
|
|
memset(dis, 0x3f, sizeof(dis));
|
|
//memset(vis,0,sizeof(vis));
|
|
//while(Q.size()) Q.pop();
|
|
dis[s] = 0;
|
|
Q.push(make_pair(0, s));
|
|
while (!Q.empty()) {
|
|
int x = Q.top().second;
|
|
Q.pop();
|
|
if (vis[x])continue;
|
|
vis[x] = 1;
|
|
for (int i = head[x]; i; i = edge[i].next) {
|
|
int y = edge[i].var;
|
|
if (dis[x] + edge[i].val < dis[y]) {
|
|
dis[y] = dis[x] + edge[i].val;
|
|
if (!vis[y])
|
|
Q.push(make_pair(-dis[y], y));
|
|
}
|
|
}
|
|
|
|
}
|
|
}
|
|
|
|
int main() {
|
|
int S;
|
|
scanf("%d %d %d", &N, &M, &S);
|
|
while (M--) {
|
|
int x, y, z;
|
|
scanf("%d %d %d", &x, &y, &z);
|
|
add(x, y, z);
|
|
}
|
|
dijkstra(S);
|
|
for (int i = 1; i <= N; i++)printf("%d ", dis[i]);
|
|
} |