锐客网

  1. 首页 > it技术 > >

UVA10048 Audiophobia （floyd变形）

题解 输入一个C个点S条边的无向带权图，边权表示该路径上的噪音值，当噪音值太大时，耳膜会受到伤害，所以当你从某点去另外一个点时，总是希望路上经过的最大噪音值最小，输入一些询问，输出这两点之间最大噪音值最小的路径。 直接用floyd算法，但是把加法改成min,min改成max。解释：不管是floyd还是dijkstra，都是基于这样一个事实：对于任意一条至少包含两条边的路径i->j，一定存在一个中间点k，使得i->j的总长度等于i->k,k->j的长度之和。对于不同的点k，i->k,k->j的长度之和可能不同，最后还需要取一个最小值才是i->j的最短路径，把刚才推理中“之和”与“取最小值”换成“取最小值”和“取最大值”，推理仍然适用 代码

#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define MAX 100005 const int INF = 1000001; #define LL long long int cas=1,T; int d[105][105]; int main() { int n,m,c; while (scanf("%d%d%d",&n,&m,&c) && n) { for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) { d[i][i]=0; d[i][j]=INF; } for (int i = 1; i<=m; i++) { int f,t,di; scanf("%d%d%d",&f,&t,&di); d[f][t]=di; d[t][f]=di; } for (int k=1; k<=n; k++) for (int i = 1; i<=n; i++) for (int j = 1; j<=n; j++) d[i][j]=min(d[i][j],max(d[i][k],d[k][j])); if (cas!=1) printf("\n"); //注意输出格式 printf("Case #%d\n",cas++); for (int i = 0; i

    推荐阅读


    上一篇：mac版本intellij配置

    下一篇：任何生命都是奇迹，这句话也适合我平凡的一生。