首页 > 代码库 > UVA 10048 Audiophobia
UVA 10048 Audiophobia
简单DP。转移就可以。比较像floyd
#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int C,S,Q;#define MAXN 110int dis[MAXN][MAXN];int main(){ //freopen("sample.txt","r",stdin); int kase = 1; bool first = false; while (scanf("%d%d%d",&C,&S,&Q)!=EOF) { if (C == 0 && S == 0 && Q == 0) break; if (first) putchar(‘\n‘); else first = true; memset(dis,-1,sizeof(dis)); for (int i = 0; i <= C; i++) dis[i][i] = 0; while (S--) { int u,v,w; scanf("%d%d%d",&u,&v,&w); dis[u][v] = dis[v][u] = w; } for (int k = 1; k <= C; k++) for (int i = 1; i <= C; i++) for (int j = 1; j <= C; j++) { if (dis[i][k] != -1 && dis[k][j] != -1) { if (dis[i][j] != -1) dis[i][j] = min (max(dis[i][k],dis[k][j]),dis[i][j]); else dis[i][j] = max(dis[i][k],dis[k][j]); } } printf("Case #%d\n",kase++); while (Q--) { int u,v; scanf("%d%d",&u,&v); if (dis[u][v] != -1) printf("%d\n",dis[u][v]); else puts("no path"); } } return 0;}
UVA 10048 Audiophobia
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。