PAT A 1018. Public Bike Management (30)【最短路径】
https://www.patest.cn/contests/pat-a-practise/1018
先用Dijkstra算出最短路,然后二分答案来验证,顺便求出剩余最小,然后再从终点dfs回去求出路径
#include<cstdio> #include<string> #include<cstring> #include<vector> #include<iostream> #include<queue> #include<algorithm> using namespace std; typedef long long LL; const int INF = 0x7FFFFFFF; const int maxn = 1e3 + 10; int c, n, s, m, f[maxn], map[maxn][maxn], x, y, z, dis[maxn], vis[maxn], ans; void dfs(int x, int y) { if (y < 0) return; if (x == s) { ans = min(ans, y); return; } for (int i = 0; i <= n; i++) { if (map[x][i] == -1) continue; if (dis[i] == dis[x] + map[x][i]) dfs(i, y - (c / 2 - f[i])); } } bool Dfs(int x, int y, int z) { if (!x) { if (y == z) { printf("0"); return true; } else return false; } for (int i = 0; i <= n; i++) { if (map[x][i] == -1) continue; if (dis[x] == dis[i] + map[x][i]) { if (Dfs(i, y + c / 2 - f[x], z)) { printf("->%d", x); return true; } } } return false; } int main() { scanf("%d%d%d%d", &c, &n, &s, &m); for (int i = 1; i <= n; i++) scanf("%d", &f[i]); memset(map, -1, sizeof(map)); memset(dis, -1, sizeof(dis)); while (m--) { scanf("%d%d%d", &x, &y, &z); if (map[x][y] == -1 || map[x][y] > z) map[x][y] = map[y][x] = z; } dis[0] = 0; while (true) { int now = -1; for (int i = 0; i <= n; i++) { if (!vis[i] && dis[i] != -1 && (now == -1 || dis[i] < dis[now])) now = i; } if (now == -1) break; vis[now] = 1; for (int i = 0; i <= n; i++) { if (map[now][i] == -1) continue; if (dis[i] == -1 || dis[i]>dis[now] + map[now][i]) dis[i] = dis[now] + map[now][i]; } } int q = 0, h = n*c / 2; while (q <= h) { int mid = q + h >> 1; ans = INF; dfs(0, mid); if (ans != INF) h = mid - 1; else q = mid + 1; } printf("%d ", q);//需要运出的数量 dfs(0, q); Dfs(s, ans, q); printf(" %d ", ans);//需要运回的数量 return 0; }