本题目要求通过读入无向网的边的信息（省略了各顶点的信息，仅用顶点编号来表示），构造图，并利用Dijkstra算法，求出指定源点到其它各点的最短路径。
输入样例:
第一行，两个整数，顶点数vN和边数eN。
以后若干行，是相关边的信息，无向图的边是对称的，只输入一半的边（小编号到大编号的，间以空格），最后两行各一个整数，前一个指定源点，后一个指定的查询的终到点。
（注意，示例中34条边，只输入了17条边的信息）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| 10 34
0 1 2
0 3 5
1 2 5
1 3 2
2 4 8
2 5 4
3 5 4
3 6 2
4 7 5
4 5 2
5 6 3
5 7 9
5 8 7
6 8 7
7 8 3
7 9 4
8 9 8
0
8
|
输出样例:
在一行中输出从源点到指定终点的短路径及代价，注意：所有符号均为西文符号。
思路：
最短路径的模板题 ，Dijkstra算法是解决单源最短路径问题的贪心算法
大体思路为先求出长度最短的一条路径，再参照该最短路径求出长度次短的一条路径，知道求出从源点到其他各个顶点的最短路径
需要注意的是：起点和终点相同的情况需要特殊判断
代码：
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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
| #include<bits/stdc++.h>
using namespace std;
typedef struct
{
int v, w;
} Node;
const int inf = 0x3f3f3f3f;
const int N = 1005;
int n, e, s, d;
int dis[N], pre[N];
vector<Node> v[N];
bool vis[N] = {false};
void dijkstra(int s)
{
fill(dis, dis + N, inf);
dis[s] = 0;
for (int i = 0; i < n; i++)
{
int u = -1, minx = inf;
for (int j = 0; j < n; j++)
{
if (!vis[j] && dis[j] < minx)
{
u = j;
minx = dis[j];
}
}
if (u == -1)
break;
vis[u] = true;
for (int j = 0; j < v[u].size(); j++)
{
int x = v[u][j].v;
if (!vis[x] && dis[u] + v[u][j].w < dis[x])
{
dis[x] = dis[u] + v[u][j].w;
pre[x] = u;
}
}
}
}
int main()
{
scanf("%d %d", &n, &e);
for (int i = 0; i < e / 2; i++)
{
int a, b, c;
scanf("%d %d %d", &a, &b, &c);
v[a].push_back(Node{b, c});
v[b].push_back(Node{a, c});
}
scanf("%d %d", &s, &d);
if (s == d)
{
printf("%d-->%d:0", s,s);
return 0;
}
dijkstra(s);
vector<int> v;
int x = d;
while (x != s)
{
v.push_back(x);
x = pre[x];
}
printf("%d", s);
for (int i = v.size() - 1; i >= 0; i--)
printf("-->%d", v[i]);
printf(":%d", dis[d]);
return 0;
}
|
