[Usaco2009 Oct]Heat Wave 热浪（裸最短路径）

链接：https://ac.nowcoder.com/acm/contest/1082/F
来源：牛客网

题目描述

The good folks in Texas are having a heatwave this summer. Their Texas Longhorn cows make for good eating but are not so adept at creating creamy delicious dairy products. 
Farmer John is leading the charge to deliver plenty of ice cold nutritious milk to Texas so the Texans will not suffer the heat too much.
FJ has studied the routes that can be used to move milk from Wisconsin to Texas. 
These routes have a total of T (1 <= T <= 2,500) towns conveniently numbered 1..T along the way (including the starting and ending towns). 
Each town (except the source and destination towns) is connected to at least two other towns by bidirectional roads that have some cost of traversal (owing to gasoline consumption, tolls, etc.). 
Consider this map of seven towns; town 5 is the source of the milk and town 4 is its destination (bracketed integers represent costs to traverse the route):
                              [1]----1---[3]-
                             /               
                      [3]---6---[4]---3--[3]--4
                     /               /       /|
                    5         --[3]--  --[2]- |
                            /        /       |
                      [5]---7---[2]--2---[3]---
                            |       /
                           [1]------
Traversing 5-6-3-4 requires spending 3 (5->6) + 4 (6->3) + 3 (3->4) = 10 total expenses.
Given a map of all the C (1 <= C <= 6,200) connections (described as two endpoints R1i and R2i (1 <= R1i <= T; 1 <= R2i <= T) and costs (1 <= Ci <= 1,000), find the smallest total expense to traverse from the starting town Ts (1 <= Ts <= T) to the destination town Te (1 <= Te <= T).

POINTS: 300

输入描述:

* Line 1: Four space-separated integers: T, C, Ts, and Te
* Lines 2..C+1: Line i+1 describes road i with three space-separated integers: R1i, R2i, and Ci

输出描述:

* Line 1: A single integer that is the length of the shortest route from Ts to Te. It is guaranteed that at least one route exists.

示例1

输入

输出

说明

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

裸最短路

刚开始写了最简单的Floyd，超时了

Floyd：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <stack>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 const int maxn=1e5+10;
17 using namespace std;
18 
19 int G[2501][2501];
20  
21 int main()
22 {
23     int T,C,Ts,Te;
24     scanf("%d %d %d %d",&T,&C,&Ts,&Te);
25     memset(G,INF,sizeof(G));
26     for(int i=1;i<=C;i++)
27     {
28         int u,v,t;
29         scanf("%d %d %d",&u,&v,&t);
30         G[u][v]=t;
31         G[v][u]=t;
32     }
33     for(int k=1;k<=T;k++)
34     {
35         for(int i=1;i<=T;i++)
36         {
37             G[i][i]=0;
38             for(int j=1;j<=T;j++)
39             {
40                 if(G[i][j]>G[i][k]+G[k][j])
41                     G[i][j]=G[i][k]+G[k][j];
42             }
43         }
44     }
45     printf("%d
",G[Ts][Te]);
46     return 0;  
47 }

Dijkstra和SPFA都可以过

SPFA：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <stack>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 const int maxn=1e5+10;
18 using namespace std;
19 //ios::sync_with_stdio(false);
20 //    cin.tie(NULL);
21 
22 struct Edge_node
23 {
24     int to;
25     int next;
26     int cost;
27 }Edge[7005<<1];
28 
29 int n,m;
30 int head[3000];
31 int cnt;
32 int dis[3000];
33 bool inqueue[3000];
34 
35 void add_edge(int u,int v,int t)
36 {
37     Edge[cnt].to=v;
38     Edge[cnt].cost=t;
39     Edge[cnt].next=head[u];
40     head[u]=cnt++;
41 } 
42 
43 void SPFA(int x)
44 {
45     queue<int> qe;
46     qe.push(x);
47     inqueue[x]=true;
48     while(!qe.empty())
49     {
50         int u=qe.front();
51         qe.pop();
52         inqueue[u]=false;
53         for(int i=head[u];i!=-1;i=Edge[i].next)
54         {
55             int v=Edge[i].to;
56             if(dis[u]+Edge[i].cost<dis[v])
57             {
58                 dis[v]=dis[u]+Edge[i].cost;
59                 if(!inqueue[v])
60                 {
61                     qe.push(v);
62                     inqueue[v]=true;
63                 }
64             }
65         }
66     }
67 }
68 
69 int main()
70 {
71     int a,b;
72     scanf("%d %d %d %d",&n,&m,&a,&b);
73     memset(dis,INF,sizeof(dis));
74     memset(head,-1,sizeof(head));
75     for(int i=1;i<=m;i++)
76     {
77         int u,v,t;
78         scanf("%d %d %d",&u,&v,&t);
79         add_edge(u,v,t);
80         add_edge(v,u,t);
81     }
82     dis[a]=0;
83     SPFA(a);
84     printf("%d
",dis[b]);
85     return 0;    
86 }

Dijkstra：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <string>
 5 #include <math.h>
 6 #include <algorithm>
 7 #include <vector>
 8 #include <queue>
 9 #include <set>
10 #include <stack>
11 #include <map>
12 #include <math.h>
13 const int INF=0x3f3f3f3f;
14 typedef long long LL;
15 const int mod=1e9+7;
16 //const double PI=acos(-1);
17 const int maxn=1e5+10;
18 using namespace std;
19 //ios::sync_with_stdio(false);
20 //    cin.tie(NULL);
21 
22 struct Edge_node
23 {
24     int to;
25     int next;
26     int cost;
27 }Edge[7005<<1];
28 
29 int n,m,a,b;
30 int head[3000];
31 int cnt;
32 int dis[3000];
33 
34 struct cmp
35 {
36     bool operator()(int x,int y)
37     {
38         return dis[x]>dis[y]; 
39     }
40 };
41 
42 void add_edge(int u,int v,int t)
43 {
44     Edge[cnt].to=v;
45     Edge[cnt].cost=t;
46     Edge[cnt].next=head[u];
47     head[u]=cnt++;
48 } 
49 
50 void Dijkstra()
51 {
52     priority_queue<int,vector<int>,cmp > qe;
53     dis[a]=0;
54     qe.push(a);
55     while(!qe.empty())
56     {
57         int u=qe.top();
58         qe.pop();
59         for(int i=head[u];i!=-1;i=Edge[i].next)
60         {
61             int v=Edge[i].to;
62             if(dis[u]+Edge[i].cost<dis[v])
63             {
64                 dis[v]=dis[u]+Edge[i].cost;
65                 qe.push(v);
66             }
67         } 
68     }
69 }
70 
71 int main()
72 {
73     scanf("%d %d %d %d",&n,&m,&a,&b);
74     memset(dis,INF,sizeof(dis));
75     memset(head,-1,sizeof(head));
76     for(int i=1;i<=m;i++)
77     {
78         int u,v,t;
79         scanf("%d %d %d",&u,&v,&t);
80         add_edge(u,v,t);
81         add_edge(v,u,t);
82     }
83     Dijkstra();
84     printf("%d
",dis[b]);
85     return 0;    
86 }