hdu1690

#include #include #include using namespace std; const long long _max = 999999999999LL; //加LL要不然报数据太大; const int maxn = 111; long long dist[maxn][maxn]; //多个距离相加 可能爆int int a[200]; int n, m; int l1,l2,l3,l4,c1,c2,c3,c4; void inint() { for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(i==j) dist[i][j] = 0; else dist[i][j] = _max; }void input() { scanf("%d%d%d%d%d%d%d%d", &l1,&l2,&l3,&l4,&c1,&c2,&c3,&c4); scanf("%d%d", &n, &m); inint(); for(int i = 1; i <= n; i++) scanf("%d", &a[i]); for(int i = 1; i <= n; i++) for(int j = i+1; j <= n; j++) { int tot = abs(a[j]-a[i]); if(tot>0 && tot<=l1) dist[i][j] = dist[j][i] = c1; else if(tot>l1&&tot<=l2) dist[i][j] = dist[j][i] = c2; else if(tot>l2&&tot<=l3) dist[i][j] = dist[j][i] = c3; else if(tot>l3&&tot<=l4) dist[i][j] = dist[j][i] = c4; //else if(tot>l4) dist[i][j] = dist[j][i] = _max; } }void flody() { for(int k = 1; k <= n; k++) for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) if(dist[i][k] != _max && dist[k][j] != _max && dist[i][j] > dist[i][k]+dist[k][j]) dist[i][j] = dist[i][k]+dist[k][j]; }void output() { static int z = 1; printf("Case %d:\n", z++); for(int i = 1; i <= m; i++) { int u, v; scanf("%d%d", &u, &v); if(dist[u][v] != _max) printf("The minimum cost between station %d and station %d is %I64d.\n", u, v, dist[u][v]); else printf("Station %d and station %d are not attainable.\n", u, v); } }int main() { int t; scanf("%d", &t); //k = 0; while(t--) { //k++; input(); flody(); output(); } }


    推荐阅读