HDOJ3790 最短路径问题[Dijkstra算法||SPFA]

最短路径问题

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 4820 Accepted Submission(s): 1446

Problem Description

给你n个点，m条无向边，每条边都有长度d和花费p，给你起点s终点t，要求输出起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的。

Input

输入n,m，点的编号是1~n,然后是m行，每行4个数 a,b,d,p，表示a和b之间有一条边，且其长度为d，花费为p。最后一行是两个数 s,t;起点s，终点。n和m为0时输入结束。
(1<n<=1000, 0<m<100000, s != t)

Output

输出一行有两个数，最短距离及其花费。

Sample Input

3 2 1 2 5 6 2 3 4 5 1 3 0 0

Sample Output

9 11

Source

浙大计算机研究生复试上机考试-2010年

Recommend

notonlysuccess

前面一直WA，后来才发现不能用INT_MAX来赋值，还找了好久的问题，以后注意了!!!

code:

  1 #include <iostream>   
  2 #include <iomanip>   
  3 #include <fstream>   
  4 #include <sstream>   
  5 #include <algorithm>   
  6 #include <string>   
  7 #include <set>   
  8 #include <utility>   
  9 #include <queue>   
 10 #include <stack>   
 11 #include <list>   
 12 #include <vector>   
 13 #include <cstdio>   
 14 #include <cstdlib>   
 15 #include <cstring>   
 16 #include <cmath>   
 17 #include <ctime>   
 18 #include <ctype.h> 
 19 using namespace std;
 20 
 21 #define MAXN 1010
 22 
 23 int n,m;
 24 int s,t;
 25 int dist[MAXN];
 26 int disc[MAXN];
 27 int mapt[MAXN][MAXN];
 28 int mapc[MAXN][MAXN];
 29 int vst[MAXN];
 30 
 31 void Dijkstra()
 32 {
 33     int i,j,k;
 34     for(i=1;i<=n;i++)
 35     {
 36         dist[i]=mapt[s][i];
 37         disc[i]=mapc[s][i];
 38         vst[i]=0;
 39     }
 40     vst[s]=1;
 41     dist[s]=0;
 42     disc[s]=0;
 43     for(i=2;i<=n;i++)
 44     {
 45         k=s;
 46         int lowdis=99999;
 47         for(j=1;j<=n;j++)
 48             if(!vst[j]&&dist[j]<lowdis)
 49             {
 50                 k=j;
 51                 lowdis=dist[j];
 52             }
 53         if(lowdis==99999)
 54             break;
 55         vst[k]=1;
 56         for(j=1;j<=n;j++)
 57         {
 58             if(!vst[j])
 59             {
 60                 if(dist[j]>mapt[k][j]+dist[k])
 61                 {
 62                     dist[j]=mapt[k][j]+dist[k];
 63                     disc[j]=mapc[k][j]+disc[k];
 64                   }
 65                 else if(dist[j]==mapt[k][j]+dist[k])
 66                 {
 67                     if(disc[j]>mapc[k][j]+disc[k])
 68                         disc[j]=mapc[k][j]+disc[k];
 69                 }
 70             }
 71         }
 72     }
 73 }
 74 
 75 int main()
 76 {
 77     int i,j;
 78     int a,b,d,p;
 79     while(~scanf("%d%d",&n,&m),n&&m)
 80     {
 81         for(i=1;i<=MAXN;i++)
 82             for(j=1;j<=MAXN;j++)
 83             {
 84                 mapt[i][j]=99999;
 85                 mapc[i][j]=99999;
 86             }
 87         for(i=1;i<=m;i++)
 88         {
 89             scanf("%d%d%d%d",&a,&b,&d,&p);
 90             if(d<mapt[a][b])
 91             {
 92                 mapt[a][b]=mapt[b][a]=d;
 93                  mapc[a][b]=mapc[b][a]=p;
 94             }
 95             else if(d==mapt[a][b])
 96             {
 97                 if(p<mapc[a][b])
 98                     mapc[a][b]=mapc[b][a]=p;
 99             }
100         }
101         scanf("%d%d",&s,&t);
102         Dijkstra();
103         printf("%d %d\n",dist[t],disc[t]);
104     }
105     return 0;
106 }

SPFA

code:

 1 #include <iostream>   
 2 #include <iomanip>   
 3 #include <fstream>   
 4 #include <sstream>   
 5 #include <algorithm>   
 6 #include <string>   
 7 #include <set>   
 8 #include <utility>   
 9 #include <queue>   
10 #include <stack>   
11 #include <list>   
12 #include <vector>   
13 #include <cstdio>   
14 #include <cstdlib>   
15 #include <cstring>   
16 #include <cmath>   
17 #include <ctime>   
18 #include <ctype.h> 
19 using namespace std;
20 
21 #define MAXN 1010
22 #define intmax 99999999
23 
24 int map[MAXN][MAXN];
25 int dis[MAXN];
26 int cost[MAXN][MAXN];
27 int QM[MAXN];
28 int px[MAXN];       //费用
29 int n,m;
30 
31 void init()
32 {
33     int i,j;
34     for(i=1;i<=n;i++)
35     {
36         QM[i]=0;
37         px[i]=dis[i]=intmax;
38         for(j=1;j<=n;j++)
39             cost[i][j]=map[i][j]=intmax;
40     }
41 }
42 
43 void spfa(int sx,int ex)
44 {
45     int i,j;
46     queue<int>Que;
47     int temp;
48     Que.push(sx);
49     QM[sx]=1;
50     dis[sx]=0;
51     px[sx]=0;
52     while(!Que.empty())
53     {
54         temp=Que.front();
55         Que.pop();
56         QM[temp]=0;
57         for(i=1;i<=n;i++)
58         {
59             if(dis[i]>dis[temp]+map[temp][i])
60             {
61                 dis[i]=dis[temp]+map[temp][i];
62                 px[i]=px[temp]+cost[temp][i];
63                 if(QM[i]==0)
64                 {
65                     QM[i]=1;
66                     Que.push(i);
67                 }
68             }
69             else if(dis[i]==dis[temp]+map[temp][i]&&px[i]>px[temp]+cost[temp][i])
70             {
71                 px[i]=px[temp]+cost[temp][i];
72             }
73         }
74     }
75     printf("%d %d\n",dis[ex],px[ex]);
76 }
77 
78 int main()
79 {
80     int a,b,d,p;
81     while(~scanf("%d%d",&n,&m),n||m)
82     {
83         init();
84         for(int i=1;i<=m;i++)
85         {
86             scanf("%d%d%d%d",&a,&b,&d,&p);
87             if(d<map[a][b])
88             {
89                 map[a][b]=map[b][a]=d;
90                 cost[a][b]=cost[b][a]=p;
91             }
92         }
93         int st,et;
94         scanf("%d%d",&st,&et);
95         spfa(st,et);
96     }
97     return 0;
98 }