华师一附中OI组

标题: P3371 【模板】单源最短路径 [打印本页]

---

作者: admin    时间: 2018-5-4 10:04
标题: P3371 【模板】单源最短路径
https://www.luogu.org/problemnew/show/P3371
题目描述
如题，给出一个有向图，请输出从某一点出发到所有点的最短路径长度。

输入输出格式
输入格式：
第一行包含三个整数N、M、S，分别表示点的个数、有向边的个数、出发点的编号。

接下来M行每行包含三个整数Fi、Gi、Wi，分别表示第i条有向边的出发点、目标点和长度。

输出格式：
一行，包含N个用空格分隔的整数，其中第i个整数表示从点S出发到点i的最短路径长度（若S=i则最短路径长度为0，若从点S无法到达点i，则最短路径长度为2147483647）

输入输出样例
输入样例#1：
4 6 1
1 2 2
2 3 2
2 4 1
1 3 5
3 4 3
1 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

---

作者: admin    时间: 2021-5-17 20:30
我用一个标准的dijkstra 来做这个题，大家看看

1. #include<bits/stdc++.h>
   
2. using namespace std;
   
3. const int inf=2147483647;
   
4. const int mm=500050;
   
5. const int mn=10010;
   
6. int n,m,s;
   
7. int nxt[mm],ev[mm],ew[mm];
   
8. int dist[mn],vist[mn],nbs[mn],p[mn],heap[mn];
   
9. 
   
10. int getmin()
    
11. {
    
12.         int m,k,i;
    
13.         m=inf;
    
14.         k=0;  ///起点，无路可找的时候就返回0
    
15.         ///for (i=1;i<=n;i++)  cout<<dist[i]<<' '; cout<<endl;
    
16.         for (i=1; i<=n; i++)
    
17.                 if (!vist[i])
    
18.                         if (dist[i]<m)
    
19.                                 {
    
20.                                         m=dist[i];
    
21.                                         k=i;
    
22.                                 }
    
23.         return k;
    
24. }
    
25. 
    
26. void dijkstra(int src)
    
27. {
    
28.         int i,j,u,v,cnt=1;
    
29.         for(i=1; i<=n; i++)
    
30.                 {
    
31.                         dist[i]=inf;
    
32.                         vist[i]=0;
    
33.                 };
    
34.         dist[src]=0;
    
35.         heap[1]=src;
    
36.         while(cnt<=n)
    
37.                 {
    
38.                         u=getmin();
    
39.                         cnt++;
    
40.                         vist[u]=1;
    
41.                         for(j=nbs[u]; j!=0; j=nxt[j])
    
42.                                 {
    
43.                                         v=ev[j];
    
44.                                         if(!vist[v]&&dist[u]+ew[j]<dist[v])
    
45.                                                 {
    
46.                                                         dist[v]=dist[u]+ew[j];
    
47.                                                         p[v]=u;
    
48.                                                 }
    
49.                                 }
    
50.                 }
    
51. }
    
52. void printpath(int i)///反推路径找到S到I的路
    
53. {
    
54.         int path[mn]= {i,}; ///初始终点
    
55.         int j=0,k=i;
    
56.         while (p[k]!=0)  ///完全类似导弹飞机的倒推
    
57.                 {
    
58.                         j++;
    
59.                         path[j]=p[k];
    
60.                         k=p[k];
    
61.                 }
    
62.         cout<<s<<"-->"<<i<<':';
    
63.         for (; j>=0; j--) cout<<path[j];
    
64.         cout<<endl;
    
65. }
    
66. int main()
    
67. {
    
68.         int i,u,v,w;
    
69.         scanf("%d%d%d",&n,&m,&s);
    
70.         for(i=1; i<=n; i++)nbs[i]=0;
    
71.         for(i=1; i<=m; i++)
    
72.                 {
    
73.                         scanf("%d%d%d",&u,&v,&w);
    
74.                         nxt[i]=nbs[u];
    
75.                         nbs[u]=i;
    
76.                         ev[i]=v;
    
77.                         ew[i]=w;///这里考虑一下如何去掉重复的边，
    
78.                 }
    
79.         dijkstra(s);
    
80.         for (i=1; i<=n; i++)  printf("%d ",dist[i]);
    
81.         ///cout<<endl;
    
82.         ///for (i=1; i<=n; i++)  printpath(i);
    
83.         return 0;
    
84. }

复制代码

注意此题数据规模比较大，读入输出要用scanf和printf，否则只有70分

---

欢迎光临 华师一附中OI组 (http://hsyit.cn/)

Powered by Discuz! X3.2