hdu 3790 最短路径问题(双重权值，dijkstra算法)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3790

题目大意：题意明了，输出最短路径及其花费。

需要注意的几点：(1)当最短路径相同时，输出最小花费！！！

(2)更新路径的时候要注意更新花费。

 1 #include <iostream>
 2 #include <cstdio>
 3 using namespace std;
 4 const int INF=9999999;
 5 int map[1010][1010],Min,n,cost[1010][1010],node[1010],vis[1010];
 6 int pr[1010];
 7 
 8 void set()
 9 {
10     for (int i=1; i<=n; i++)
11     {
12         vis[i]=0;
13         node[i]=INF;
14         pr[i]=INF;
15         for (int j=1; j<=n; j++)
16         {
17             map[i][j]=INF;
18             cost[i][j]=INF;
19         }
20     }
21 }
22 
23 void dijkstra(int m)
24 {
25     int tm=m;
26     vis[m]=1;
27     node[m]=0;
28     pr[m]=0;
29     for (int k=2; k<=n; k++)
30     {
31         Min=INF;
32         int M=INF;
33         for (int i=1; i<=n; i++)
34             if(!vis[i])
35             {
36                 if (node[i]>map[tm][i]+node[tm])
37                 {
38                     node[i]=map[tm][i]+node[tm];
39                     pr[i]=cost[tm][i]+pr[tm];
40                 }
41                 else if(node[i]==map[tm][i]+node[tm])
42                 {
43                     if(pr[i]>cost[tm][i]+pr[tm])
44                     {
45                         node[i]=map[tm][i]+node[tm];
46                         pr[i]=cost[tm][i]+pr[tm];
47                     }
48                 }
49                 if (Min>node[i])
50                 {
51                     M=pr[i];
52                     Min=node[i];
53                     m=i;
54                 }
55                 else if (Min==node[i])
56                 {
57                     if(M>pr[i])
58                     {
59                         M=pr[i];
60                         Min=node[i];
61                         m=i;
62                     }
63                 }
64             }
65         vis[m]=1;
66         tm=m;
67     }
68 }
69 
70 int main ()
71 {
72     int a,b,d,p,m;
73     while(scanf("%d%d",&n,&m),n||m)
74     {
75         set();
76         while (m--)
77         {
78             scanf("%d%d%d%d",&a,&b,&d,&p);
79             if (map[a][b]>d)
80             {
81                 cost[a][b]=cost[b][a]=p;
82                 map[a][b]=map[b][a]=d;
83             }
84             else if (map[a][b]==d)
85             {
86                 if (cost[a][b]>p)
87                     cost[a][b]=cost[b][a]=p;
88             }
89         }
90         scanf("%d%d",&a,&b);
91         dijkstra(a);
92         printf ("%d %d
",node[b],pr[b]);
93     }
94 }

一种简单明了的代码。

  1 #include <iostream>
  2 #include <cstdio>
  3 
  4 using namespace std;
  5 
  6 const int INF=9999999;
  7 
  8 int Map[1010][1010],Min,Mmin,n,cost[1010][1010],node[1010],vis[1010];
  9 int pr[1010],tm;
 10 
 11 void sett()
 12 {
 13     for (int i=1; i<=n; i++)
 14     {
 15         node[i]=INF;
 16         vis[i]=0;
 17         pr[i]=INF;
 18         for (int j=1; j<=n; j++)
 19         {
 20             Map[i][j]=INF;
 21             cost[i][j]=INF;
 22         }
 23     }
 24 }
 25 
 26 int dijkstra()
 27 {
 28     for (int i=1; i<=n; i++)
 29     {
 30         Min=INF;
 31         Mmin=INF;
 32         for (int j=1; j<=n; j++)
 33         {
 34             if (!vis[j])
 35             {
 36                 if (Min>node[j])
 37                 {
 38                     Min=node[j];
 39                     Mmin=pr[j];
 40                     tm=j;
 41                 }
 42                 else if (Min==node[j])
 43                 {
 44                     if (Mmin>pr[j])
 45                     {
 46                         Mmin=pr[j];
 47                         tm=j;
 48                     }
 49                 }
 50             }
 51         }
 52         vis[tm]=1;
 53         for (int j=1; j<=n; j++)
 54             if (!vis[j])
 55             {
 56                 if (node[j]>Map[tm][j]+node[tm])
 57                 {
 58                     node[j]=Map[tm][j]+node[tm];
 59                     pr[j]=cost[tm][j]+pr[tm];
 60                 }
 61                 else if (node[j]==Map[tm][j]+node[tm])
 62                 {
 63                     if (pr[j]>cost[tm][j]+pr[tm])
 64                     {
 65                         node[j]=Map[tm][j]+node[tm];
 66                         pr[j]=cost[tm][j]+pr[tm];
 67                     }
 68                 }
 69             }
 70     }
 71 }
 72 
 73 int main ()
 74 {
 75     int m,a,b,d,p,s,t;
 76     while (~scanf("%d%d",&n,&m))
 77     {
 78         if (n==0&&m==0)
 79             break;
 80         sett();
 81         for (int i=1; i<=m; i++)
 82         {
 83             scanf("%d%d%d%d",&a,&b,&d,&p);
 84             if (Map[a][b]>d)
 85             {
 86                 Map[a][b]=Map[b][a]=d;
 87                 cost[a][b]=cost[b][a]=p;
 88             }
 89             else if (Map[a][b]==d)
 90             {
 91                 if (cost[a][b]>p)
 92                     cost[a][b]=cost[b][a]=p;
 93             }
 94         }
 95         scanf("%d%d",&s,&t);
 96         node[s]=0;
 97         pr[s]=0;
 98         dijkstra();
 99         printf ("%d %d
",node[t],pr[t]);
100     }
101 }

View Code