hdu 1690 Bus System ---Floyd
点击打开链接
这道题用Floyd更方便。。
#include <iostream>#include <stdio.h>#include <memory.h>#include <cmath>using namespace std;const long long INF = 99999999999LL; //注意！要加LL，不然会报错数据太大const int N = 105;int l1, l2, l3, l4, c1, c2, c3, c4;long long map[N][N]; //距离可能会爆int，所以用long longint place[N];int n, m;void init(){ int i, j; for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(i == j) map[i][j] = 0; else map[i][j] = INF;}void input(){ int i, j, len; scanf("%d%d%d%d%d%d%d%d", &l1, &l2, &l3, &l4, &c1, &c2, &c3, &c4); scanf("%d %d", &n, &m); init(); for(i = 1; i <= n; i++) { scanf("%d", &place[i]); } for(i = 1; i <= n; i++) { for(j = i+1; j <= n; j++) { len = abs(place[i] - place[j]); if(0 < len && len <= l1) map[i][j] = map[j][i] = c1; else if(l1 < len && len <= l2) map[i][j] = map[j][i] = c2; else if(l2 < len && len <= l3) map[i][j] = map[j][i] = c3; else if(l3 < len && len <= l4) map[i][j] = map[j][i] = c4; } }}void floyd() //这题绝对是用floyd方便{ int i, j, k; for(k = 1; k <= n; k++) for(i = 1; i <= n; i++) for(j = 1; j <= n; j++) if(map[i][j] > map[i][k] + map[k][j]) map[i][j] = map[i][k] + map[k][j];}void output(){ int ti, tj; static int zz = 1; printf("Case %d:\n", zz++); while(m--) { scanf("%d %d", &ti, &tj); if(map[ti][tj] != INF) printf("The minimum cost between station %d and station %d is %I64d.\n", ti, tj, map[ti][tj]); else printf("Station %d and station %d are not attainable.\n", ti, tj); }}int main(){ int t; scanf("%d", &t); while(t--) { input(); floyd(); output(); } return 0;}