你的weight数组初始化是几
by kdlkswb @ 2017-11-07 20:24:55
是-1,输入时比当前weight值大则覆盖.
by VAdams @ 2017-11-07 20:30:17
我再把问题描述的详细点~
“噪音恐惧症”(Audiophobia) 是求图某两点间最大权最小的路径,本题似乎是求图中某两点间最小权最大的路径?
分别贴上“Audiophobia”的正确代码(来自rujia liu大师)
以及本题本萌新的错误代码(自造小范围数据能过):
```cpp
// UVa10048 Audiophobia
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn = 100 + 5;
const int INF = 1000000000;
int d[maxn][maxn];
int main() {
int n, m, Q, u, v, w, kase = 0;
while(scanf("%d%d%d", &n, &m, &Q) == 3 && n) {
// 初始化
for(int i = 0; i < n; i++) {
d[i][i] = 0;
for(int j = i+1; j < n; j++) { d[i][j] = d[j][i] = INF; }
}
for(int i = 0; i < m; i++) {
scanf("%d%d%d", &u, &v, &w); u--; v--;
d[u][v] = min(d[u][v], w);
d[v][u] = d[u][v];
}
// 主算法
for(int k = 0; k < n; k++)
for(int i = 0; i < n; i++)
for(int j = 0; j < n; j++)
if(d[i][k] < INF && d[k][j] < INF)
d[i][j] = min(d[i][j], max(d[i][k], d[k][j]));
// 询问
if(kase) printf("\n");
printf("Case #%d\n", ++kase);
while(Q--) {
scanf("%d%d", &u, &v); u--; v--;
if(d[u][v] == INF) printf("no path\n"); else printf("%d\n", d[u][v]);
}
}
return 0;
}
```
-----------货车运输--------------
```cpp
#include<stdio.h>
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int n,m;int map[1010][1010];int weight[1010][1010];
int wmax(int a,int b){
if(a>b) return a;
else return b;
}
int wmin(int a,int b){
if(a<b) return a;
else return b;
}
int main(){
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) map[i][j]=-1; //memset(map,-1,sizeof(map));
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) weight[i][j]=-1;
for(int i=1;i<=n;i++){ weight[i][i]=0; }
int i,j,w;for(int k=1;k<=m;k++){ //建图.
scanf("%d %d %d",&i,&j,&w);
map[i][j]=max(map[i][j],w);//if((map[i][j]!=-1 && w<map[i][j]) || map[i][j]==-1) map[i][j]=w;
map[j][i]=map[i][j];
weight[i][j]=map[i][j];weight[j][i]=map[i][j];
}
for(int k=1;k<=n;k++){
for(int u=1;u<=n;u++){
for(int v=1;v<=n;v++){
if(map[u][k]!=-1 && map[k][v]!=-1){
weight[u][v]=wmax(wmin(weight[u][k],weight[k][v]),weight[u][v]);
weight[v][u]=weight[u][v];
}
}
}
}
int q;scanf("%d",&q);int x,y;
for(int i=1;i<=q;i++){
scanf("%d %d",&x,&y);//weight[x][y]
printf("%d\n",weight[x][y]);
}
return 0;
}
```
by VAdams @ 2017-11-07 20:44:30
啊……忘记用回复功能了 @[kdlkswb](/space/show?uid=8592) dalao
by VAdams @ 2017-11-07 20:55:01
@[mk\_within](/space/show?uid=29207) 解决了,应该赋INF 来着……
by VAdams @ 2017-11-07 21:19:28