算法课复习 -- 图、Dijkstra 算法课复习

HDU #1874 : 畅通工程续
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1874
题意：n个点m条边的无向图，给定s和t，问从s到t的最短路。
思路：单源最短路，dijkstra即可。
AC代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define P pair #define ll long long #define ull unsigned long long #define lson id*2,l,mid #define rson id*2+1,mid+1,r #define ls id*2 #define rs (id*2+1) #define Mod(a,b) a G[maxn]; int dis[maxn]; struct cmp { bool operator()(node a, node b) { return a.dis > b.dis; } }; int dij() { priority_queue, cmp> que; que.push(node{ s,0 }); dis[s] = 0; while (!que.empty()) { node u = que.top(); que.pop(); if (u.id == t) return u.dis; for (int i = 0; i < G[u.id].size(); i++) { node v = G[u.id][i]; if (dis[v.id] == -1 || dis[u.id] + v.dis < dis[v.id]) { dis[v.id] = dis[u.id] + v.dis; que.push(node{ v.id,dis[v.id] }); } } } return -1; }int main() { while (~scanf("%d%d", &n, &m)) { for (int i = 0; i < n; i++) G[i].clear(); cl1(dis); while (m--) { scanf("%d%d%d", &x, &y, &z); G[x].push_back(node{ y,z }); G[y].push_back(node{ x,z }); } scanf("%d%d", &s, &t); int ans = dij(); printf("%d\n", ans); } return 0; }

HDU #1596 : find the safest road
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=1596
题意：有n个城市，给出两两间的安全度（0~1之间），问从s到t一路上的安全度之积最大为多少。
思路：由于0~1之间的数相乘只会变小或相等，因此可以用最短路的方法来求最大安全度之积。对于询问都做一遍dijkstra即可。
AC代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define P pair #define ll long long #define ull unsigned long long #define lson id*2,l,mid #define rson id*2+1,mid+1,r #define ls id*2 #define rs (id*2+1) #define Mod(a,b) a, cmp> que; for (int i = 1; i <= n; i++) dis[i] = -1; dis[x] = 1; que.push(node{ x, dis[x] }); while (!que.empty()) { node u = que.top(); que.pop(); if (u.id == y) { if (u.dis == 0) puts("What a pity!"); else printf("%.3f\n", u.dis); return; } for (int i = 1; i <= n; i++) { if (i == u.id)continue; if (dis[u.id] * cnt[u.id][i] > dis[i]) { dis[i] = dis[u.id] * cnt[u.id][i]; que.push(node{ i,dis[i] }); } } } }int main() { while (~scanf("%d", &n)) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) scanf("%lf", &cnt[i][j]); } scanf("%d", &m); while (m--) { scanf("%d%d", &x, &y); dij(); } } return 0; }

51Nod #1459 : 迷宫游戏
传送门：https://www.51nod.com/Challenge/Problem.html#!#problemId=1459
题意：n个房间m条路，每条路有花费的时间t和获得的得分s，问在花最短时间的前提下，最高得分为多少。
思路：单源最短路，不过要多记一个得分。
当第一次走到终点时，记录当前的时间t并继续进行搜索并更新得分，直到所需的时间>t时才结束搜索。
AC代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define P pair #define ll long long #define ull unsigned long long #define lson id*2,l,mid #define rson id*2+1,mid+1,r #define ls id*2 #define rs (id*2+1) #define Mod(a,b) a G[510]; int score[510]; int dis[510]; int n, m, start, endd; int ans_t, ans_s; struct cmp { bool operator()(node1 a, node1 b) { return a.dis > b.dis; } }; void dij() { priority_queue, cmp> que; que.push(node1{ start,score[start],0 }); dis[start] = 0; while (!que.empty()) { node1 u = que.top(); que.pop(); if (u.dis > ans_t)return; if (u.id == endd) { ans_t = min(ans_t, u.dis); ans_s = max(ans_s, u.score); continue; } for (int i = 0; i < G[u.id].size(); i++) { node v = G[u.id][i]; if (dis[v.v] == -1 || u.dis + v.dis <= dis[v.v]) { dis[v.v] = u.dis + v.dis; que.push(node1{ v.v,u.score + score[v.v],u.dis + v.dis }); } } } }int main() { while (~scanf("%d%d%d%d", &n, &m, &start, &endd)) { cl1(dis); ans_s = -1; ans_t = INF; for (int i = 0; i < n; i++) scanf("%d", &score[i]); while (m--) { scanf("%d%d%d", &x, &y, &z); G[x].push_back(node{ y,z }); G[y].push_back(node{ x,z }); } dij(); printf("%d %d\n", ans_t, ans_s); } return 0; }

POJ #2253 : Frogger
传送门：http://poj.org/problem?id=2253
题意：给出n个平面坐标上的点，问所有从点1到达点2的方法中，过程中的最大距离的最小值为多少。
思路：单源最短路，但这里最短的不是总体距离而是每次的距离，所以dis数组记录的东西改变一下就可以了。
（PE的每个case最后要空行）
AC代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define P pair #define ll long long #define ull unsigned long long #define lson id*2,l,mid #define rson id*2+1,mid+1,r #define ls id*2 #define rs (id*2+1) #define Mod(a,b) a b.dis; } }; double cal(int aa, int bb) { return sqrt((a[aa].x - a[bb].x)*(a[aa].x - a[bb].x) + (a[aa].y - a[bb].y)*(a[aa].y - a[bb].y)); }void dij() { priority_queue, cmp> que; for (int i = 1; i <= n; i++) { dis[i] = cal(1, i); que.push(node{ i,dis[i] }); } while (!que.empty()) { node u = que.top(); que.pop(); if (u.id == 2) { printf("Frog Distance = %.3f\n", u.dis); break; } for (int i = 1; i <= n; i++) { if (i == u.id)continue; double d = cal(u.id, i); d = max(d, u.dis); if (d < dis[i]) { dis[i] = d; que.push(node{ i,dis[i] }); } } } }int main() { int _ = 1; while (~scanf("%d", &n)) { if (n == 0)break; for (int i = 1; i <= n; i++) dis[i] = INF; for (int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].x, &a[i].y); printf("Scenario #%d\n", _); dij(); printf("\n"); _++; } return 0; }

HDU #2680 : Choose the best route
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=2680
题意：n个点m条边的有向图，给定多个起点和一个终点，问从起点到终点最短距离是多少。
思路：把终点看作起点做dijkstra，取起点中距离最近的点就是答案。
AC代码：

#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define P pair #define ll long long #define ull unsigned long long #define lson id*2,l,mid #define rson id*2+1,mid+1,r #define ls id*2 #define rs (id*2+1) #define Mod(a,b) a G[maxn]; int cost[maxn][maxn]; int dis[maxn]; struct node { int id; int dis; }; struct cmp { bool operator()(node a, node b) { return a.dis > b.dis; } }; void dij() { priority_queue, cmp> que; que.push(node{ endd,0 }); dis[endd] = 0; while (!que.empty()) { node u = que.top(); que.pop(); for (int i = 0; i < G[u.id].size(); i++) { int v = G[u.id][i]; if (dis[v] == -1 || dis[v] > u.dis + cost[u.id][v]) { dis[v] = u.dis + cost[u.id][v]; que.push(node{ v,dis[v] }); } } } }int main() { while (~scanf("%d%d%d", &n, &m, &endd)) { for (int i = 1; i <= n; i++) G[i].clear(); cl1(cost); cl1(dis); while (m--) { scanf("%d%d%d", &x, &y, &z); G[y].push_back(x); if (cost[y][x] == -1 || cost[y][x] > z) cost[y][x] = z; } dij(); int ans = INF; scanf("%d", &w); while (w--) { scanf("%d", &x); if (dis[x] != -1) ans = min(ans, dis[x]); } if (ans == INF)ans = -1; printf("%d\n", ans); } return 0; }