HDU 1874 畅通工程续 戳我直达
题意：求s到t的最短路径。最简单的最短路径题。
做法：Dijkstra 或 floyd
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include <bits/stdc++.h>#define scf0(a) scanf("%s",&a)#define scf1(a) scanf("%d",&a)#define scf2(a,b) scanf("%d%d",&a,&b)#define scf3(a,b,c) scanf("%d%d%d",&a,&b,&c)#define MEM(a,b) memset(a,b,sizeof(a))#define pii pair<int,int>#define pdd pair<double,double>#define LL long longusing namespace std;const int INF = 0x3f3f3f3f;const double eps = 1e-8;const int maxn = 200 + 10;int mp[maxn][maxn];int n, m, s, t, u, v, w;int Dijkstra(int s, int t) { //初始化 int dist[maxn]; bool vis[maxn]; MEM(vis,false); for(int i = 0; i < n; i++) dist[i] = mp[s][i]; dist[s] = 0; vis[s] = true; //循环n - 1次 for(int j = 0; j < n - 1; j++) { //初始化 int minn = INF, pos; //找最小点 for(int i = 0; i < n; i++) { if(vis[i]) continue; if(dist[i] < minn) pos = i, minn = dist[i]; } vis[pos] = true; //更新最短路径 for(int i = 0; i < n; i++) { if(vis[i]) continue; dist[i] = min(dist[i], dist[pos] + mp[pos][i]); } } return dist[t] < INF ? dist[t] : -1;}int main() { while(~scf2(n, m)) { MEM(mp, INF); for(int i = 0; i < m; i++) { scf3(u, v, w); if(w < mp[u][v]) mp[u][v] = mp[v][u] = w; //输入的小坑...两点之间可能不止两条路线 } scf2(s, t); printf("%d
", Dijkstra(s, t) ); }} |
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
#include <bits/stdc++.h>#define scf0(a) scanf("%s",&a)#define scf1(a) scanf("%d",&a)#define scf2(a,b) scanf("%d%d",&a,&b)#define scf3(a,b,c) scanf("%d%d%d",&a,&b,&c)#define MEM(a,b) memset(a,b,sizeof(a))#define pii pair<int,int>#define pdd pair<double,double>#define LL long longusing namespace std;const int INF = 0x3f3f3f3f;const double eps = 1e-8;const int maxn = 200 + 10;int mp[maxn][maxn];int n, m, s, t, u, v, w;int floyd(int s, int t) //无fuck说，不想懂{ for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++) mp[i][j]=mp[j][i]=min(mp[i][j],mp[i][k]+mp[k][j]); return mp[s][t] < INF ? mp[s][t] : -1;}int main() { while(~scf2(n, m)) { MEM(mp, INF); for(int i = 0; i < m; i++) { scf3(u, v, w); if(w < mp[u][v]) mp[u][v] = mp[v][u] = w; //输入的小坑...两点之间可能不止两条路线 } scf2(s, t); if(s == t) puts("0"); //相同始终点，floyd最终得到的0 else printf("%d
", floyd(s, t) ); }} |