UVa-383, Live Archive-5430, TJU-1572, POJ-1529, ZOJ-1285 : Shipping Routes
問題概要
ノード数V(<30)のグラフで全点間最短路を求める問題。
解法
Warshall-Floyd。入出力が面倒。オンラインジャッジごとに必要なスペースの数が違う。
acceptされたコード
計算量O(V^3)。
#include <cstdio> #include <algorithm> #include <map> #include <string> using namespace std; const int MAX_N = 30; const int INF = 1<<29; map<string, int> get_id; char buf1[30], buf2[30]; int N, M, Q; int graph[MAX_N][MAX_N]; void init(){ scanf("%d%d%d ", &N, &M, &Q); get_id.clear(); for(int i=0; i<N; i++){ scanf(" %s ", buf1); get_id[string(buf1)] = i; } for(int i=0; i<N; i++){ fill(graph[i], graph[i] + N, INF); } for(int i=0; i<M; i++){ scanf(" %s %s ", buf1, buf2); graph[get_id[string(buf1)]][get_id[string(buf2)]] = graph[get_id[string(buf2)]][get_id[string(buf1)]] = 1; } } void solve(){ for(int k=0; k<N; k++){ for(int i=0; i<N; i++){ for(int j=0; j<N; j++){ graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]); } } } for(int i=0; i<Q; i++){ int d, len; scanf(" %d %s %s ", &d, buf1, buf2); len = graph[get_id[string(buf1)]][get_id[string(buf2)]]; if(len == INF){ puts("NO SHIPMENT POSSIBLE"); } else{ printf("$%d\n", d*len*100); } } } int main(){ int T; scanf("%d",&T); puts("SHIPPING ROUTES OUTPUT\n"); for(int c=1; c<=T; c++){ printf("DATA SET %d\n\n", c); init(); solve(); puts(""); } puts("END OF OUTPUT"); return 0; }