hdu 3790 最短路径问题

最短路径问题

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

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 | We have carefully selected several similar problems for you: 2544 2066 1217 2112 1142

16570349

2016-03-16 13:33:03

Accepted

3790

405MS

5144K

2391B

C++

czy

题意：

求起点到终点的最短距离及其花费，如果最短距离有多条路线，则输出花费最少的

注意：

用优先队列的dijikstra，注意判断，对已经处理过的点，要直接舍弃掉

1 if(Dis[te.to] < te.dis) continue;
2 if(Dis[te.to] == te.dis && Cost[te.to] < te.cost) continue;

代码：

  1 #include <cstdio>
  2 #include <cstring>
  3 #include <iostream>
  4 #include <algorithm>
  5 #include <stack>
  6 #include <cctype>
  7 #include <vector>
  8 #include <cmath>
  9 #include <map>
 10 #include <queue>
 11 
 12 #define ll long long
 13 #define eps 1e-8
 14 #define N 1004
 15 #define inf 0x3ffffffffffffff
 16 
 17 using namespace std;
 18 
 19 int n,m;
 20 
 21 struct PP
 22 {
 23     friend bool operator < (PP n1,PP n2)
 24     {
 25         if(n1.dis == n2.dis){
 26             return n1.cost < n2.cost;
 27         }
 28         else{
 29             return n1.dis < n2.dis;
 30         }
 31     }
 32     int to;
 33     ll dis;
 34     ll cost;
 35 };
 36 
 37 int s,t;
 38 ll Dis[N],Cost[N];
 39 
 40 vector<PP> G[N];
 41 
 42 void add_adge(int a,int b,ll d,ll q)
 43 {
 44     PP te;
 45     te.to = b;te.dis = d;te.cost = q;
 46     G[a].push_back(te);
 47     te.to = a;
 48     G[b].push_back(te);
 49 }
 50 
 51 void ini()
 52 {
 53     int i;
 54     for(i = 0;i <= n;i++){
 55         G[i].clear();
 56     }
 57     fill(Dis,Dis+N,inf);
 58     fill(Cost,Cost+N,inf);
 59     int a,b;
 60     ll d,p;
 61     while(m--){
 62         scanf("%d%d%I64d%I64d",&a,&b,&d,&p);
 63         add_adge(a,b,d,p);
 64     }
 65     scanf("%d%d",&s,&t);
 66     Dis[s] = Cost[s] = 0;
 67 }
 68 
 69 void dijikstra()
 70 {
 71     priority_queue<PP> que;
 72     PP te,nt;
 73     te.to = s;te.dis = te.cost = 0;
 74     que.push(te);
 75     while(!que.empty())
 76     {
 77         te = que.top();
 78         que.pop();
 79         unsigned int i;
 80         if(Dis[te.to] < te.dis) continue;
 81         if(Dis[te.to] == te.dis && Cost[te.to] < te.cost) continue;
 82         for(i = 0 ;i < G[te.to].size();i++){
 83             nt.to = G[te.to][i].to;
 84             nt.dis = G[te.to][i].dis;
 85             nt.cost = G[te.to][i].cost;
 86             if(Dis[nt.to] > Dis[te.to] + nt.dis){
 87                 que.push(nt);
 88                 Dis[nt.to] = Dis[te.to] + nt.dis;
 89                 Cost[nt.to] = Cost[te.to] + nt.cost;
 90             }
 91             else if( (Dis[nt.to] == Dis[te.to] + nt.dis) &&  (Cost[nt.to] > Cost[te.to] + nt.cost) ){
 92                 que.push(nt);
 93                 Dis[nt.to] = Dis[te.to] + nt.dis;
 94                 Cost[nt.to] = Cost[te.to] + nt.cost;
 95             }
 96         }
 97     }
 98 }
 99 
100 int main()
101 {
102     //freopen("in.txt","r",stdin);
103     //scanf("%d",&T);
104     //for(int ccnt=1;ccnt<=T;ccnt++){
105     while(scanf("%d%d",&n,&m)!=EOF){
106         if(n == 0 && m == 0) break;
107         ini();
108         dijikstra();
109         printf("%I64d %I64d
",Dis[t],Cost[t]);
110     }
111     return 0;
112 }