AOJ_0117 A reward for a Carpenter
問題
解法
有向グラフの最短経路を求める問題。
ワーシャルフロイド法をつかえば十分はやく求まる。
#include <cstdio> #include <algorithm> using namespace std; const int INF = 1 << 29; const int MAX_N = 21; int G[MAX_N][MAX_N]; int N, s, g; int HOUBI, HASHIRA; int w(){ for(int k = 0; k < N; k++){ for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ G[i][j] = min(G[i][j], G[i][k] + G[k][j]); } } } return G[s][g] + G[g][s]; } int main(){ int m; int a, b, c, d; scanf("%d", &N); scanf("%d", &m); for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ G[i][j] = INF; //初期化 }} for(int i = 0; i < m; i++){ scanf("%d, %d, %d, %d", &a, &b, &c, &d); a--; b--; G[a][b] = c; G[b][a] = d; } scanf("%d, %d, %d, %d", &s, &g, &HOUBI, &HASHIRA); s--; g--; printf("%d\n", HOUBI - HASHIRA - w()); return 0; }