最短路径问题 HDU 3790

最短路径问题

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

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

Sample Output

9 11

Source

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

Recommend

notonlysuccess | We have carefully selected several similar problems for you: 1874 2066 1217 2112 1142

傻X了，在比较花费大小时，写成了p[e.to] = min(p[e.to],p[v]+e.cost) 实际上花费是附属于最短路径的，确定了路径，花费也就确定了，QAQ，搞了一中午。。。

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 using namespace std;
 8 const int INF = 0x3f3f3f3f;
 9 struct edge{
10     int to,dis,cost;
11 };
12 vector<edge> g[1005];
13 typedef pair<int,int> pa; //第一元素是距离，第二元素是编号
14 int d[1005],p[1005];
15 int s,t;
16 void dijkstra(){
17     memset(d,INF,sizeof(d));
18     memset(p,INF,sizeof(p));
19     d[s] = 0;
20     p[s] = 0;
21     priority_queue< pa, vector<pa>, greater<pa> > q;
22     q.push(pa(0,s));
23     while(!q.empty()){
24         pa cur = q.top(); q.pop();
25         int v = cur.second;
26         if(d[v]<cur.first) continue;
27         for(int i = 0; i<g[v].size(); i++){
28             edge e = g[v][i];
29             if(d[e.to] >= d[v]+e.dis){
30                 d[e.to] = d[v]+e.dis;
31                 p[e.to] = p[v]+e.cost;
32                 q.push(pa(d[e.to],e.to));
33             }
34         }
35     }
36 }
37 void solve(){
38     int n,m;
39     while(scanf("%d%d",&n,&m) == 2 && n && m){
40         for(int i = 0; i<m; i++){
41             int a,b,c,p;
42             scanf("%d%d%d%d",&a,&b,&c,&p);
43             g[a].push_back((edge){b,c,p});
44             g[b].push_back((edge){a,c,p});
45         }
46         scanf("%d%d",&s,&t);
47         dijkstra();
48         printf("%d %d
",d[t],p[t]);
49         for(int i = 0; i<1005; i++) g[i].clear();
50     }
51 }
52 int main(){
53     solve();
54 }

第两种写法：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <queue>
 7 using namespace std;
 8 const int INF = 0x3f3f3f3f;
 9 struct edge{
10     int to,dis,cost;
11     friend bool operator < (edge A,edge B){
12         if(A.dis!=B.dis) return A.dis>B.dis;
13         else return A.cost>B.cost;
14     }
15 };
16 vector<edge> g[1005];
17 //typedef pair<int,int> pa; //第一元素是距离，第二元素是编号
18 int d[1005],p[1005];
19 bool done[1005];
20 int s,t;
21 void dijkstra(){
22     memset(d,INF,sizeof(d));
23     memset(p,INF,sizeof(p));
24     memset(done,false,sizeof(done));
25     d[s] = 0;
26     p[s] = 0;
27     priority_queue<edge> q;
28     q.push((edge){s,0,0});
29     while(!q.empty()){
30         edge cur = q.top(); q.pop();
31         int v = cur.to;
32         if(done[v]) continue;
33         done[v] = true;
34         for(int i = 0; i<g[v].size(); i++){
35             edge e = g[v][i];
36             if((d[e.to] > d[v]+e.dis)||(d[e.to] == d[v]+e.dis&&p[e.to]>p[v]+e.cost)){
37                 d[e.to] = d[v]+e.dis;
38                 p[e.to] = p[v]+e.cost;
39                 q.push((edge){e.to,d[e.to],p[e.to]});
40             }
41         }
42     }
43 }
44 void solve(){
45     int n,m;
46     while(scanf("%d%d",&n,&m) == 2 && n && m){
47         for(int i = 0; i<m; i++){
48             int a,b,c,p;
49             scanf("%d%d%d%d",&a,&b,&c,&p);
50             g[a].push_back((edge){b,c,p});
51             g[b].push_back((edge){a,c,p});
52         }
53         scanf("%d%d",&s,&t);
54         dijkstra();
55         printf("%d %d
",d[t],p[t]);
56         for(int i = 0; i<1005; i++) g[i].clear();
57     }
58 }
59 int main(){
60     solve();
61 }