-
- 17.5K通过
- 56.1K提交
- 题目提供者HansBug 站长团
- 评测方式云端评测
- 标签O2优化高性能
- 难度普及/提高-
- 时空限制1000ms / 128MB
- 提示：收藏到任务计划后，可在首页查看。
最新讨论显示
推荐的相关题目显示
题目背景
本题测试数据为随机数据，在考试中可能会出现构造数据让SPFA不通过，如有需要请移步 P4779。
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。
接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。
输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）
输入输出样例
说明
时空限制：1000ms,128M
数据规模：
对于20%的数据：N<=5，M<=15；
对于40%的数据：N<=100，M<=10000；
对于70%的数据：N<=1000，M<=100000；
对于100%的数据：N<=10000，M<=500000。保证数据随机。
#include<bits/stdc++.h> using namespace std; #define inf 0x3f3f3f3f using namespace std; int n, m; struct node { int to, cost; }; struct node2 { bool friend operator < (node2 n1, node2 n2) { return n1.d > n2.d; } int id, d; }; vector<node>g[200000+10]; bool finish[200000+10]; int dis[200000+10]; void myinit() { memset(finish, 0, sizeof(finish)); for(int i = 0; i < 200001; i++) { g[i].clear(); } memset(dis, inf, sizeof(dis)); } void dijkstra(int s) { priority_queue<node2> q; dis[s] = 0; node2 nn1; nn1.id = s; nn1.d = dis[s]; q.push(nn1); while(!q.empty()) { node2 nn2 = q.top(); q.pop(); int now = nn2.id; if(finish[now])continue; else finish[now] = 1; for(int i = 0; i < g[now].size(); i++) { if(!finish[g[now][i].to] && g[now][i].cost + dis[now] < dis[g[now][i].to]) { dis[g[now][i].to] = g[now][i].cost + dis[now]; } node2 nn3; nn3.id = g[now][i].to; nn3.d = dis[g[now][i].to]; q.push(nn3); } } } int main() { int i, j, x, y, c, s, t; while(scanf("%d%d%d", &n, &m,&s)!=EOF) { myinit(); for(i = 0; i < m; i++) { scanf("%d%d%d", &x, &y, &c); node n1; n1.to = y; n1.cost = c; g[x].push_back(n1); } dijkstra(s); for(t=1;t<=n;t++){ if(dis[t] == inf) cout<<"2147483647"; else cout<<dis[t]; if(t==n)printf("\n"); else printf(" "); } } return 0; }