最短路专题
kuangbin带你飞专题4最短路
A
一个很裸的最短路问题,但是我又又又被卡了好久啊。
因为可能会有重边,而且数据读入的顺序和我平时的顺序不太一样,导致一直被卡。。。
B
是一个完全图,最后特别要注意一个东西!
printf() 函数中不存在 %lf ,输入 double 用 %lf 输出用 %f
输出格式害人一直以为的东西竟然是错的emmm
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
| #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <queue> using namespace std; const int maxn = 205; double dis[maxn]; double G[maxn][maxn]; struct Node{ int x, y; }point[maxn]; int n; double cal(int x1, int y1, int x2, int y2){ return sqrt(1.0*(x1-x2)*(x1-x2)+1.0*(y1-y2)*(y1-y2)); } const double INF = 1e9; typedef pair<double, int> P; void dijk(){ for(int i=0; i<n; i++) dis[i] = INF; int s = 0; dis[s] = 0; priority_queue<P, vector<P>, greater<P> > pq; pq.push(P(0, s)); while(!pq.empty()){ P temp = pq.top(); pq.pop(); int u = temp.second; if(dis[u]<temp.first) continue; for(int i=0; i<n; i++){ if(dis[i]>max(dis[u], G[u][i])){ dis[i] = max(dis[u], G[u][i]); pq.push(P(dis[i], i)); } } } printf("Frog Distance = %.3f\n\n", dis[1]); } int main(){ int kase = 0; while(~scanf("%d", &n)&&n){ int x, y; for(int i=0; i<n; i++){ scanf("%d%d", &point[i].x, &point[i].y); } for(int i=0; i<n; i++){ for(int j=0; j<i; j++){ if(i == j) G[i][j] = 0; else { G[i][j] = cal(point[i].x, point[i].y, point[j].x, point[j].y); G[j][i] = G[i][j]; } } } printf("Scenario #%d\n", ++kase); dijk(); } return 0; }
|
c
要求找到一个路径从1到n,使得这条路径上的最小的边权最大
还是用不断的拓展的思想,每次用最大的边进行拓展,所以优先队列用less<P>
, 然后注意dis[]的初始化,应该还是比较的简单的。
关键就是不断拓展的思想
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
| #include <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <vector> #include <queue> using namespace std; const int maxn = 1e3+10; struct Node{ int v, weight; }; vector<Node> G[maxn]; int n, m; typedef pair<int, int> P; int dis[maxn]; const int INF = 1e9; void dijk(int s){ for(int i=0; i<maxn; i++) dis[i] = -1; priority_queue<P, vector<P>, less<P> > pq; pq.push(P(0, s)); dis[s] = INF; while(!pq.empty()){ P temp = pq.top(); pq.pop(); int u = temp.second; if(temp.first>dis[u]) continue; for(int i=0; i<G[u].size(); i++){ int v = G[u][i].v; int weight = G[u][i].weight; if(dis[v]<min(dis[u], weight)){ dis[v] = min(dis[u], weight); pq.push(P(dis[v], v)); } } } return; } int main() { int t; scanf("%d", &t); int kase = 1; while(t--){ scanf("%d%d", &n, &m); for(int i=0; i<maxn; i++) G[i].clear(); for(int i=0; i<m; i++){ int u, v, weight; scanf("%d%d%d", &u, &v, &weight); G[u].push_back(Node{v, weight}); G[v].push_back(Node{u, weight}); } printf("Scenario #%d:\n", kase++); dijk(1); printf("%d\n\n", dis[n]); } return 0; }
|
D
反向建边,跑单源最短路
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65
| #include <cstdio> #include <queue> #include <cstring> #include <cmath> #include <vector> using namespace std; const int maxn = 1e3+10; struct Edge{ int v, weight; }; typedef pair<int, int> P; vector<Edge> G1[maxn]; vector<Edge> G2[maxn]; int dis1[maxn]; int dis2[maxn]; const int INF = 1e9; int n, m, x; void dijk(vector<Edge> *G, int *dis){ for(int i=0; i<=n; i++) dis[i] = INF; dis[x] = 0; priority_queue<P, vector<P>, greater<P> > pq; pq.push(P(0, x)); while(!pq.empty()){ P temp = pq.top(); pq.pop(); int u = temp.second; if(temp.first>dis[u]) continue; for(int i=0; i<G[u].size(); i++){ int v = G[u][i].v; int weight = G[u][i].weight; if(dis[v]>dis[u]+weight){ dis[v] = dis[u]+weight; pq.push(P(dis[v], v)); } } } return; } int main() { while(~scanf("%d%d%d", &n, &m, &x)){ int u, v, weight; for(int i=0; i<maxn; i++){ G1[i].clear(); G2[i].clear(); } for(int i=0; i<m; i++){ scanf("%d%d%d", &u, &v, &weight); G1[u].push_back(Edge{v, weight}); G2[v].push_back(Edge{u, weight}); } dijk(G2, dis2); dijk(G1, dis1); int ans = -1; for(int i=1; i<=n; i++){ if(i == x) continue; else ans = max(ans, dis1[i]+dis2[i]); } printf("%d\n", ans); } return 0; }
|
未解决的问题