首页 > 代码库 > 洛谷 P3371 【模板】单源最短路径
洛谷 P3371 【模板】单源最短路径
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。
输入输出格式
输入格式：第一行包含三个整数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
有向图单源最短路模板
1 #include<iostream> 2 #include<cstdio> 3 #include<queue> 4 using namespace std; 5 const int MAX_E = 500010, MAX_P = 10010, INF = 2147483647; 6 typedef pair<int, int> pii; 7 priority_queue<pii, vector<pii>, greater<pii> > q; 8 struct edge { 9 int v, w, next;10 } e[MAX_E];11 int head[MAX_P], dis[MAX_P], tot, n, m, s;12 bool vis[MAX_P];13 void add(int a, int b, int c) {14 e[++tot].v = b;15 e[tot].w = c;16 e[tot].next = head[a];17 head[a] = tot;18 }19 void init() {20 int i;21 for (i = 1; i <= n; i++) {22 head[i] = -1;23 dis[i] = INF;24 }25 } 26 void dijkstra(int s) {27 int i;28 dis[s] = 0;29 q.push(make_pair(dis[s], s));30 while (!q.empty()) {31 pii tmp = q.top();32 q.pop();33 int x = tmp.second;34 if(vis[x]) continue;35 else {36 vis[x] = true;37 for(i = head[x]; i + 1; i = e[i].next) {38 if(dis[e[i].v] > dis[x] + e[i].w) {39 dis[e[i].v] = dis[x] + e[i].w;40 q.push(make_pair(dis[e[i].v], e[i].v)); 41 }42 }43 }44 }45 }46 int main() {47 scanf("%d%d%d", &n, &m, &s);48 int i, f, g, w;49 init();50 for (i = 1; i <= m; i++) {51 scanf("%d%d%d", &f, &g, &w);52 add(f, g, w);53 }54 dijkstra(s);55 for (i = 1; i <= n; i++) 56 printf("%d ", dis[i]);57 return 0;58 }
洛谷 P3371 【模板】单源最短路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。