C - Heavy Transportation dijkstra POJ - 1797

93 阅读 0 评论 62 点赞

我是靠谱客的博主爱撒娇冰淇淋，这篇文章主要介绍C - Heavy Transportation dijkstra POJ - 1797，现在分享给大家，希望可以做个参考。

N个点，M条边，每条边有权值。求一条1号点到N号点的路径，要求使得路径中的边权最小值最大。

Input

多组输入，第一行给一个T。
每一组第一行给两个数n和m。（1 <= n <= 1000）
接下来m行，每行三个数u，v，w代表路径的两个端点与边权。
（1 <= u，v <= n ， 0< w <= 1e6）
保证两点间只有一条边，该图为无向图。

Output

第i组数据先输出 "Scenario #i:"
然后输出该路径上的最小边权。
保证有解

Sample Input

1
3 3
1 2 3
1 3 4
2 3 5

Sample Output

Scenario #1:
4

题意就是让找，各个路径中最小的那条边的最大值

比如 3 ->5 和 4，第一条路径最小的是3，第二条路径最小的是4，那么4就是最小的之中最大的。

做法就是改改松弛操作，dist[j] = max(min(dist[u],a[u][j]));

还要注意的是这里的dist意义不再是1到某点的最短路径，而是到某个点的路径中的最小边的最大值，不难理解，但是要记得把之前代码中，求的也不是最小，而是取最大，还有在init时初始化是-INF.

复制代码

#include"stdio.h"
#include"algorithm"
#include"cstring"
#include"iostream"
#define maxn 1005
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int a[maxn][maxn];
int dist[maxn];
int vst[maxn];
void init()
{
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
if(i==j)
{
a[i][j] = 0;
}
else
{
a[i][j] = -INF;
a[j][i]= -INF;
}
}
}
}
void dijkstra()
{
for (int i = 1; i <= n; i++) {
dist[i] = a[1][i];
}
dist[1]=0;
vst[1]=1;
for(int i =
2;i <= n;i ++)
{
int u = -1,mxxx=-INF;
for(int j = 1;j <= n;j ++)
{
if(vst[j] == 0 && dist[j] > mxxx)
{
u=j;
mxxx=dist[j];
}
}
vst[u]=1;
for(int j = 1;j <= n;j ++)
{
if(vst[j] == 0)
{
int maxx = min(dist[u],a[u][j]);
if(maxx > dist[j])
{
dist[j]=maxx;
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
int h = 1;
while(t--)
{
scanf("%d %d",&n,&m);
int t1,t2,t3;
memset(dist,INF,sizeof(dist));
memset(vst,0,sizeof(vst));
init();
for(int i = 0;i < m;i ++)
{
scanf("%d %d %d",&t1,&t2,&t3);
a[t1][t2]=t3;
a[t2][t1]=t3;
}
dijkstra();
printf("Scenario #%d:n",h++);
printf("%dnn",dist[n]);
}
return 0;
}

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include"stdio.h"
#include"algorithm"
#include"cstring"
#include"iostream"
#define maxn 1005
#define INF 0x3f3f3f3f
using namespace std;
int n,m;
int a[maxn][maxn];
int dist[maxn];
int vst[maxn];
void init()
{
for(int i = 1;i <= n;i ++)
{
for(int j = 1;j <= n;j ++)
{
if(i==j)
{
a[i][j] = 0;
}
else
{
a[i][j] = -INF;
a[j][i]= -INF;
}
}
}
}
void dijkstra()
{
for (int i = 1; i <= n; i++) {
dist[i] = a[1][i];
}
dist[1]=0;
vst[1]=1;
for(int i =
2;i <= n;i ++)
{
int u = -1,mxxx=-INF;
for(int j = 1;j <= n;j ++)
{
if(vst[j] == 0 && dist[j] > mxxx)
{
u=j;
mxxx=dist[j];
}
}
vst[u]=1;
for(int j = 1;j <= n;j ++)
{
if(vst[j] == 0)
{
int maxx = min(dist[u],a[u][j]);
if(maxx > dist[j])
{
dist[j]=maxx;
}
}
}
}
}
int main()
{
int t;
scanf("%d",&t);
int h = 1;
while(t--)
{
scanf("%d %d",&n,&m);
int t1,t2,t3;
memset(dist,INF,sizeof(dist));
memset(vst,0,sizeof(vst));
init();
for(int i = 0;i < m;i ++)
{
scanf("%d %d %d",&t1,&t2,&t3);
a[t1][t2]=t3;
a[t2][t1]=t3;
}
dijkstra();
printf("Scenario #%d:n",h++);
printf("%dnn",dist[n]);
}
return 0;
}