3268 Silver Cow Party
牛パーティー。N個の農場があって、２農場間を繋ぐパスがM個ある。
各農場に1からNというナンバリングをしたとき、X (1 <= X <= N)で牛パーティーが催される。
各農場から代表牛が参加する時、行き帰りの距離が最大になる牛の移動距離を求める問題。（ただし、各牛は最短の経路を選ぶ）
ダイクストラの出番。
初めてのダイクストラを3328 Cliff Climbingで学ぶという
荒行を乗り越えたものとしては簡単な問題だった！
3328 Cliff Climbingをhalwhiteやororogに教えてもらいながら
やっていたとき、一見ちゃんと書けているのにすごく遅いコードを書いてしまった。結局原因がわからないまま放置してあるのだけど、
今回も最初はすごく遅くてTLEになってしまった。
原因は開催地から各農場までの復路の距離を毎回ダイクストラを走らせて求めていたというお粗末なものに加えて、
パスを保存する手段として２次元配列を使っていたこともあった。
２次元配列を使うと、コーディングは簡単になるけど、
疎なグラフを保存する場合、
１）存在しないパスにも0や-1を代入しておくなどメモリの無駄遣い
２）ある点iからある点jへのパスの有無をpath[i][j]を参照して確認しなければならないという時間の無駄遣い
といった弊害がある。
こういうことから、パスの保存にはvector
こうすることで、ある点iからある点jへコストwのパスが存在する場合のみpath[i]にEdge(j, w)をpush_backしてやればよいので、
メモリ節約ができ、iから移動可能な点はpath[i]を辿れば得られるので、時間の短縮もできる。
まず、２次元配列を用いたコード(1407MS)
/* * int path[1001][1001]で各農場間のパスを保存する * そのため疎なグラフの場合、 * 1) メモリの無駄遣い * 2) ある農場からある農場へのパスの有無の確認という実行時間の無駄遣い * といった弊害がある */ #include<cstdio> #include<queue> #include<cstring> #include<climits> #include<cmath> using namespace std; int N; int path[1001][1001]; struct State{ int n, w; State (int n, int w) : n(n), w(w) {} bool operator < (const State &s) const { return w > s.w; } }; int dijkstra(int s, int e, int label[]) { priority_queue<State> pq; bool visited[N+1]; for (int i = 0; i <= N; ++i) label[i] = INT_MAX; memset(visited, false, sizeof(visited)); label[s] = 0; pq.push(State(s, 0)); while (!pq.empty()) { int n = pq.top().n; int w = pq.top().w; pq.pop(); if (visited[n]) continue; visited[n] = true; if (n == e) break; for (int nn = 1; nn <= N; ++nn) { if (nn == n) continue; if (path[n][nn] != -1) { if (label[nn] > w + path[n][nn]) { label[nn] = w + path[n][nn]; pq.push(State(nn, w + path[n][nn])); } } } } return label[e]; } int main() { int M, X; scanf("%d %d %d", &N, &M, &X); memset(path, -1, sizeof(path)); for (int i = 0; i < M; ++i) { int A, B, T; scanf("%d %d %d", &A, &B, &T); path[A][B] = T; } int dist[N+1]; dijkstra(X, -1, dist); int ans = INT_MIN; for (int s = 1; s <=N; ++s) { if (s == X) continue; int dist1, dist2; int label[N+1]; dist1 = dijkstra(s, X, label); dist2 = dist[s]; ans = max(ans, dist1 + dist2); } printf("%d\n", ans); }
vector
/* * vector<Edge> pathで農場間のパスを保存する * そのため、疎なグラフであっても、 * 無駄なパスを保存しないためメモリ節約になり、 * また、ある農場からある農場へのパスの有無の確認が不要である */ #include<cstdio> #include<queue> #include<cstring> #include<climits> #include<cmath> using namespace std; int N; struct State{ int n, w; State (int n, int w) : n(n), w(w) {} bool operator < (const State &s) const { return w > s.w; } }; struct Edge{ int n, w; Edge(int n, int w) : n(n), w(w) {} }; vector<Edge> path[1001]; int dijkstra(int s, int e, int label[]) { priority_queue<State> pq; bool visited[N+1]; for (int i = 0; i <= N; ++i) label[i] = INT_MAX; memset(visited, false, sizeof(visited)); label[s] = 0; pq.push(State(s, 0)); while (!pq.empty()) { int n = pq.top().n; int w = pq.top().w; pq.pop(); if (visited[n]) continue; visited[n] = true; if (n == e) break; for (int i = 0; i < path[n].size(); ++i) { int nn = path[n][i].n; if (nn == n) continue; if (label[nn] > w + path[n][i].w) { label[nn] = w + path[n][i].w; pq.push(State(nn, w + path[n][i].w)); } } } return label[e]; } int main() { int M, X; scanf("%d %d %d", &N, &M, &X); for (int i = 0; i < M; ++i) { int A, B, T; scanf("%d %d %d", &A, &B, &T); path[A].push_back(Edge(B, T)); } int dist[N+1]; dijkstra(X, -1, dist); int ans = INT_MIN; for (int s = 1; s <=N; ++s) { if (s == X) continue; int dist1, dist2; int label[N+1]; dist1 = dijkstra(s, X, label); dist2 = dist[s]; ans = max(ans, dist1 + dist2); } printf("%d\n", ans); }
圧倒的ではないか！
