小记:我开始写的spfa,然后一直wa。。。后来改成Floyd,就a了。
思路:Floyd多源最短路。注意下INF的值要调大点,我的是1e18.
我的spfa不晓得哪里错了。
代码:spfa
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <string> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define REP(a,b,c) for(int a = b; a < c; ++a) #define eps 10e-8 const int MAX_ = 101; const int N = 100010; const long long INF = 1e18; int n; struct node{ int s, t; }p[MAX_*30]; int g[MAX_][MAX_], tmp[MAX_]; long long d[MAX_]; bool vis[MAX_]; int m, cnt, L[5],C[5]; void spfa(int start) { queue<int > q; REP(i, 0, n+1){ vis[i] = 0; d[i] = INF; } vis[start] = 1; d[start] = 0; q.push(start); while(!q.empty()){ int cur = q.front(); q.pop(); vis[cur] = 0; REP(i, 0, n){ if(g[cur][i] && d[i] > d[cur] + g[cur][i]){ d[i] = d[cur] + g[cur][i]; if(!vis[i]){ vis[i] = 1; q.push(i); } } } } return ; } int main(){ int T, ss, tt, v, Ca = 0, s, t; char str[10]; scanf("%d", &T); while(T-- &&scanf("%d%d%d%d%d%d%d%d", &L[1],&L[2],&L[3],&L[4],&C[1],&C[2],&C[3],&C[4])){ scanf("%d%d", &n, &m); //mst(g, 0); REP(i, 0, n){ scanf("%d", &tmp[i]); } REP(i, 0, n){ long long s, t; s = tmp[i]; REP(j, i+1, n){ t = s- tmp[j]; if(t < 0)t = -t; int temp = 0; REP(k, 1, 5){ if(t <= L[k]){temp = C[k];break;} } g[i][j] = g[j][i] = temp; } } /* REP(i, 0, n){ REP(j, 0, n){ printf("%d ", g[i][j]); }putchar('\n'); }*/ <span style="white-space:pre"> </span>printf("Case %d:\n", ++Ca); REP(i, 0, m){ scanf("%d%d", &s, &t); spfa(s-1); long long ans = d[t-1]; if(ans == INF){ printf("Station %d and station %d are not attainable.\n", s, t); } else printf("The minimum cost between station %d and station %d is %I64d.\n", s, t, ans); } } return 0; }
Floyd:
#include <iostream> #include <stdio.h> #include <string.h> #include <math.h> #include <stdlib.h> #include <map> #include <set> #include <vector> #include <stack> #include <queue> #include <algorithm> #include <string> using namespace std; #define mst(a,b) memset(a,b,sizeof(a)) #define REP(a,b,c) for(int a = b; a < c; ++a) #define eps 10e-8 const int MAX_ = 101; const int N = 100010; //const int INF = 0x7fffffff; const long long INF = 1e18; int n; struct node{ int s, t; }p[MAX_*30]; long long g[MAX_][MAX_], L[5],C[5], tmp[MAX_]; long long d[MAX_]; bool vis[MAX_]; int m, cnt; long long find(int t) { REP(k, 1, 5){ if(t <= L[k]){return C[k];} } return INF; } void floyd() { REP(k, 0, n)REP(i, 0, n)REP(j, 0, n){ if(g[i][j] > g[i][k] + g[k][j]){ g[i][j] = g[i][k] + g[k][j]; } } } int main(){ int T, ss, tt, v, Ca = 0, s, t; char str[10]; scanf("%d", &T); while(T-- &&scanf("%I64d%I64d%I64d%I64d%I64d%I64d%I64d%I64d", &L[1],&L[2],&L[3],&L[4],&C[1],&C[2],&C[3],&C[4])){ scanf("%d%d", &n, &m); REP(i, 0, n)REP(j, 0, n)g[i][j] = INF; REP(i, 0, n){ scanf("%I64d", &tmp[i]); } REP(i, 0, n){ long long s, t; s = tmp[i]; REP(j, i+1, n){ t = s- tmp[j]; if(t < 0)t = -t; /*long long temp; REP(k, 0, 4){ if(t <= L[k]){temp = C[k];break;} } */ g[i][j] = g[j][i] = find(t); } } /* REP(i, 0, n){ REP(j, 0, n){ printf("%I64d ", g[i][j]); }putchar('\n'); } */ floyd(); /* REP(i, 0, n){ REP(j, 0, n){ printf("%I64d ", g[i][j]); }putchar('\n'); } */ printf("Case %d:\n", ++Ca); REP(i, 0, m){ scanf("%d%d", &s, &t); //spfa(s-1); //long long ans = d[t-1]; if(g[s-1][t-1] == INF){ printf("Station %d and station %d are not attainable.\n", s, t); } else printf("The minimum cost between station %d and station %d is %I64d.\n", s, t, g[s-1][t-1]); } } return 0; }