- 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）
输入输出样例
输入样例#1： 复制
4 6 11 2 22 3 22 4 11 3 53 4 31 4 4
输出样例#1： 复制
0 2 4 3
说明
时空限制：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;}最短路径dijs+优先队列 ?模板
原文地址：https://www.cnblogs.com/djf666/p/9369830.html