題目鏈接

題意

單向圖，N - 1個牛去聚會，求所有牛去聚會和回家路徑和的最大值

AC

• 很騷的操作
  首先從派對的地方跑Dijkstra求出回家的最短路，然后將所有邊翻轉再次從聚會跑Dijkstra就是所有牛到聚會的最短路
  一共跑 2 個Dijkstra

using namespace std; int inf = 0x3f3f3f3f; int g[N][N]; int temp[N], dis[N]; bool vis[N]; bool vis_c[N][N]; void Dijkstra(int start, int n) {mem(dis, inf);mem(vis, false);dis[start] = 0;for (int i = 1; i <= n; ++i) {int MIN = inf, u = -1;for (int j = 1; j <= n; ++j) {if (vis[j]) continue;if (dis[j] < MIN) {MIN = dis[j];u = j;}}if (u == -1) return;vis[u] = true;for (int j = 1; j <= n; ++j) {if (g[u][j] == inf || vis[j]) continue;if (dis[j] > dis[u] + g[u][j]) {dis[j] = dis[u] + g[u][j];}}} }int main(){ // freopen("in.txt", "r", stdin);int n, m, x;cin >> n >> m >> x;mem(g, inf);for (int i = 0; i < m; ++i) {int u, v, c;cin >> u >> v >> c;g[u][v] = min(g[u][v], c);}// 牛回家的最短路Dijkstra(x, n);for (int i = 1; i <= n; ++i) {temp[i] = dis[i];}// 翻轉邊mem(vis_c, false);for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {if (g[i][j] != inf && vis_c[i][j] == false) {swap(g[i][j], g[j][i]);vis_c[j][i] = vis_c[i][j] = true;}}}// 牛去派對的最短Dijkstra(x, n);int ans = 0;for (int i = 1; i <= n; ++i) {temp[i] += dis[i];ans = max(ans, temp[i]);}cout << ans << endl;return 0; }

• 堆優化Dijkstra
  一共跑N + 1 個Dijkstra

using namespace std; int inf = 0x3f3f3f3f; struct ac{int v, c; }; vector<ac> g[N]; int dis[N], temp[N]; bool vis[N]; void Dijkstra(int start, int n) {mem(dis, inf);mem(vis, false);dis[start] = 0;priority_queue<P, vector<P>, greater<P> > que;que.push(P(0, start));while (!que.empty()) {P f = que.top();int v = f.second;int c = f.first;que.pop();if (dis[v] < c || vis[v]) continue;vis[v] = true;for (int j = 0; j < g[v].size(); ++j) {ac t = g[v][j];if (vis[t.v]) continue;if (dis[t.v] > c + t.c) {dis[t.v] = c + t.c;que.push(P(dis[t.v], t.v));}}}}int main(){// freopen("in.txt", "r", stdin);int n, m, x;cin >> n >> m >> x;for (int i = 0; i < m; ++i) {int u, v, c;cin >> u >> v >> c;g[u].push_back((ac){v, c});}// 牛回家的最短路Dijkstra(x, n);for (int i = 1; i <= n; ++i) {temp[i] = dis[i];}int ans = 0;// 每個牛去聚會的最短路for (int i = 1; i <= n; ++i) {if (i == x) continue;Dijkstra(i, n);temp[i] += dis[x];ans = max(temp[i], ans);}cout << ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的POJ 3268 Silver Cow Party的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。