hdu3790最短路问题

最短路径问题

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

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年

分析：

这个问题较最短路问题多了一个限制条件即如果有多条最短路的话选择花费最小的

最后够输出的是length和cost

肿么办？每条路都算一下然后再算花费？

去哦们这样考虑：
用DIJ算法

进行松弛操作的时候只要对cost单独处理即可

比如原点到某个点的直接距离为l，通过一个中介点到达这个点的距离也是l 但是花费却小那么需要更新cost

如果松弛之后距离变短那么二者均要更新

代码：

  1 #include <iostream>
  2 #include <stdio.h>
  3 #include <string.h>
  4 using namespace std;
  5 
  6 const int maxn=1005;
  7 int length[maxn][maxn];
  8 int cost[maxn][maxn];
  9 int n;
 10 int len[maxn];
 11 int cos[maxn];
 12 const int INF = 0xffffff;
 13 
 14 void clear_len(int n)
 15 {
 16     for(int i = 0; i <= n; i++)
 17     {
 18         for(int j = 0; j <= n; j++)
 19         {
 20             length[i][j] = INF;
 21         }
 22     }
 23 }
 24 
 25 void clear_cost(int n)
 26 {
 27     for(int i = 0; i <= n; i++)
 28     {
 29         for(int j = 0; j <= n; j++)
 30         {
 31             cost[i][j] = INF;
 32         }
 33     }
 34 }
 35 
 36 void DIJ(int start_point)
 37 {
 38     for(int i = 1; i <= n;i++)
 39     {
 40         len[i] = length[start_point][i];
 41         cos[i] = cost[start_point][i];
 42     }
 43     len[start_point] = 0;
 44     cos[start_point] = 0;
 45 
 46     bool flag[maxn] = { 0 };
 47     flag[start_point] = true;
 48 
 49     for(int i = 2; i <= n; i++)
 50     {
 51         int min = INF;
 52         int k;
 53         for(int j = 1; j <= n; j++)
 54         {
 55             if(!flag[j] && min > len[j])
 56             {
 57                 min = len[j];
 58                 k = j;
 59             }
 60         }
 61         flag[k] = 1;
 62         for(int j = 1; j <=n; j++)
 63         {
 64             if(!flag[j] && len[k] + length[k][j] < len[j])
 65             {
 66                 len[j] = len[k] + length[k][j];
 67                 cos[j] = cos[k] + cost[k][j];
 68             }
 69             if(!flag[j] && len[k] + length[k][j] == len[j])
 70             {
 71                 if(cos[k] + cost[k][j] < cos[j])
 72                 {
 73                     cos[j] = cos[k] + cost[k][j];
 74                 }
 75             }
 76         }
 77     }
 78 }
 79 
 80 int main()
 81 {
 82     int m;
 83     int a,b,d,p;
 84     int start_point,end_point;
 85     while(scanf("%d %d",&n,&m) && n+m)
 86     {
 87         clear_len(n);
 88         clear_cost(n);
 89         while(m--)
 90         {
 91             scanf("%d %d %d %d",&a, &b, &d, &p);
 92             if(length[a][b]==INF){
 93             length[a][b] = length[b][a] = d;
 94             cost[a][b] = cost[b][a] = p;
 95             }
 96             else
 97             {
 98                 if(length[a][b] > d)
 99                 {
100                     length[a][b] = length[b][a] = d;
101                     cost[a][b] = cost[b][a] = p;
102                 }
103                 else if(length[a][b] == d && cost[a][b] > p)
104                 {
105                     length[a][b] = length[b][a] = d;
106                     cost[a][b] = cost[b][a] = p;
107                 }
108             }
109         }
110         scanf("%d %d",&start_point, &end_point);
111         DIJ(start_point);
112         printf("%d %d
",len[end_point],cos[end_point]);
113     }
114     return 0;
115 }

View Code