TYVJ P1031 热浪 Label:dijkstra 最短路

背景

USACO OCT09 9TH

描述

德克萨斯纯朴的民眾们这个夏天正在遭受巨大的热浪！！！他们的德克萨斯长角牛吃起来不错，可是他们并不是很擅长生產富含奶油的乳製品。Farmer John此时以先天下之忧而忧，后天下之乐而乐的精神，身先士卒地承担起向德克萨斯运送大量的营养冰凉的牛奶的重任，以减轻德克萨斯人忍受酷暑的痛苦。

FJ已经研究过可以把牛奶从威斯康星运送到德克萨斯州的路线。这些路线包括起始点和终点先一共经过T (1 <= T <= 2,500)个城镇，方便地标号為1到T。除了起点和终点外地每个城镇由两条双向道路连向至少两个其它地城镇。每条道路有一个通过费用（包括油费，过路费等等）。考虑这个有7个城镇的地图。城镇5是奶源，城镇4是终点（括号内的数字是道路的通过费用）。

经过路线5-6-3-4总共需要花费3 (5->6) + 4 (6->3) + 3 (3->4) = 10的费用。

给定一个地图，包含C (1 <= C <= 6,200)条直接连接2个城镇的道路。每条道路由道路的起点Rs，终点Re (1 <= Rs <= T; 1 <= Re <= T)，和花费(1 <= Ci <= 1,000)组成。求从起始的城镇Ts (1 <= Ts <= T)到终点的城镇Te(1 <= Te <= T)最小的总费用。

输入格式

* 第一行: 4个由空格隔开的整数: T, C, Ts, Te

* 第2到第C+1行: 第i+1行描述第i条道路。有3个由空格隔开的整数: Rs, Re和Ci

输出格式

* 第一行: 一个单独的整数表示Ts到Te的最短路的长度。（不是费用麼？怎麼突然变直白了
——译者注）数据保证至少存在一条道路。

测试样例1

输入

7 11 5 4
2 4 2
1 4 3
7 2 2
3 4 3
5 7 5
7 3 3
6 1 1
6 3 4
2 4 3
5 6 3
7 2 1

输出

7

备注

5->6->1->4 (3 + 1 + 3)

代码

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<cstdio> 
 5 #include<vector>
 6 #include<queue>
 7 #define INF 0x3f3f3f3f
 8 using namespace std;
 9 struct edge{
10     int to,cost;
11 };
12 struct city{
13     int num,dist;
14 };
15 struct cmp{
16     bool operator ()(city a,city b){
17         return a.dist > b.dist;//最小值优先 
18     }
19 };
20 vector<edge> G[6300];//G[i]属于vector类型 存城市i所有的边 
21 priority_queue<city,vector<city>,cmp> que;//存城市 
22 
23 int d[6300],C,T,rs,rt;
24 
25 void init_(){
26     scanf("%d%d%d%d",&T,&C,&rs,&rt);//城市T 道路C 源点rs 汇点rt 
27     for(int i = 1;i <= C;i++){
28         int a,b,c;
29         scanf("%d%d%d",&a,&b,&c);
30         
31         edge x;
32         x.to = b;
33         x.cost = c;
34         
35         G[a].push_back(x);//存边 
36         
37         x.to = a;
38         
39         G[b].push_back(x);
40     }
41     fill(d,d + T + 1,INF);
42 }
43 
44 void dijkstra(int s){
45     d[s] = 0;
46     city x;x.dist = 0;x.num = s;
47     que.push(x);
48     
49     while(!que.empty()){//如果还有城市 
50         x = que.top();que.pop();
51         int v = x.num;
52         
53         if(d[v]<x.dist) continue;//这句话不写也可以,不是很懂什么意思,不写还快了30ms,QAQ?
54         
55         for(int i = 0;i < G[v].size();++i){
56             edge e = G[v][i];
57             if(d[e.to] > d[v] + e.cost){
58                 d[e.to] = d[v] + e.cost;
59                 
60                 city c1;c1.dist = d[e.to];c1.num = e.to;
61                 
62                 que.push(c1);
63             }
64         }
65     }
66 }
67 
68 int main(){
69 //  freopen("01.txt","r",stdin);
70     init_();
71     dijkstra(rs);
72     printf("%d
",d[rt]);
73     return 0;
74 }

以上由《挑战程序设计竞赛》P102 的代码改编(略长)

以下是hzwer黄学长的代码:http://hzwer.com/8162.html

 1 #include<cmath>
 2 #include<queue>
 3 #include<cstdio>
 4 #include<vector>
 5 #include<cstring>
 6 #include<iostream>
 7 #include<algorithm>
 8 #define pa pair<int,int>
 9 #define inf 1000000000
10 #define ll long long
11 using namespace std;
12 int T,C,Ts,Te;
13 int dis[2505];
14 bool vis[2505];
15 vector<int>e[2505],c[2505];
16 priority_queue<pa,vector<pa>,greater<pa> >q;
17 void dijkstra()
18 {
19     memset(dis,127/3,sizeof(dis));
20     q.push(make_pair(0,Ts));dis[Ts]=0;
21     while(!q.empty())
22     {
23         int now=q.top().second;q.pop();
24         if(vis[now])continue;vis[now]=1;
25         for(int i=0;i<e[now].size();i++)
26             if(dis[now]+c[now][i]<dis[e[now][i]])
27             {
28                 dis[e[now][i]]=dis[now]+c[now][i];
29                 q.push(make_pair(dis[e[now][i]],e[now][i]));
30             }
31     }
32 }
33 int main()
34 {
35     scanf("%d%d%d%d",&T,&C,&Ts,&Te);
36     for(int i=1;i<=C;i++)
37     {
38         int u,v,w;
39         scanf("%d%d%d",&u,&v,&w);
40         e[u].push_back(v);
41         e[v].push_back(u);
42         c[u].push_back(w);
43         c[v].push_back(w);
44     }
45     dijkstra();
46     printf("%d
",dis[Te]);
47     return 0;
48 }

黄学长原话:

求Ts到Te的最短路，随便选种算法写都可以

这里给出的是堆优化的dijkstra