There are two main solutions to the shortest path algorithm:
1. Dijestra algorithm for single source:
One point to all points. The main feature is to take the starting point as the center and expand outward layer by layer until it reaches the end point. Dijkstra algorithm is very useful
Representative shortest path algorithm
Algorithm details:
a. Initially, S only contains the source point, that is, S = {v}, and the distance of v is 0. U contains other vertices except v, i.e. u = {other vertices}. If v has an edge with vertex u in U, then < u, v > has weight normally. If u is not the adjacent contact of v, then < u, v > weight is ∞.
b. Select a vertex K with the smallest distance v from U and add K to S (the selected distance is the shortest path length from v to k).
c. Taking k as the newly considered middle point, modify the distance of each vertex in U; If the distance from source point v to vertex u (passing through vertex k) is shorter than the original distance (not passing through vertex k), modify the distance value of vertex u, and the distance of vertex k of the modified distance value plus the weight on the edge.
d. Repeat steps b and c until all vertices are included in S
double f(int m) {
double dis[500];
bool book[500] = {0};
fill(dis, dis + 500, inf);
for (int i = 0; i < 500; i++) dis[i] = inf;
dis[m] = 0;
for (int i = 1; i <= n * 4 - 1; i++) {
int minn = inf, u = -1;
for (int j = 1; j <= n * 4; j++) {
if (book[j] == false && dis[j] < minn) {
minn = dis[j];
u = j;
}
}
if (u == -1) break;
book[u] = true;
for (int k = 1; k <= n * 4; k++) {
if (e[u][k] < inf && dis[k] > e[u][k] + dis[u]) {
dis[k] = e[u][k] + dis[u];
}
}
}
The first is a point. For all points (n-1), find the shortest path. Secondly, find out whether there is any other third party (E [u] [k] < inf & & dis [k] > e [u] [k] + dis [u]). It is responsible for replacing the shortest path
Keep cycling until all points
2. Multi source floyd algorithm
An algorithm for solving the shortest path between any two points
Floyd algorithm is a classical dynamic programming algorithm. First, our goal is to find the shortest path from point i to point j. From the point of view of dynamic programming, we need to reinterpret this goal. This interpretation is the most creative essence of dynamic programming.
Algorithm details:
The shortest path from any node i to any node j is no more than two possibilities: 1 is directly from I to j, and 2 is from I through several nodes K to J. Therefore, we assume that Dis(i,j) is the shortest path distance from node u to node v. for each node K, we check whether dis (I, K) + dis (k, J) < Dis(i,j) is true. If it is true, it is proved that the path from I to K and then to j is shorter than the path from I to j directly, so we set Dis(i,j) = Dis(i,k) + Dis(k,j). In this way, when we traverse all nodes K, Dis(i,j) records the distance of the shortest path from I to J.
for (int i = 0; i < n * 4; i++)
for (int j = 0; j < n * 4; j++)
pri[i][j] = pri[j][i] = getp(i, j);
for (int i = 0; i < n * 4; i++)
for (int j = 0; j < n * 4; j++) {
if (i == j) continue;
for (int k = 0; k < n * 4; k++) {
if (j == k || i == k) continue;
pri[i][j] = pri[j][i] = min(pri[i][j], pri[i][k] + pri[j][k]);
}
}
3. Problem description
It's summer vacation again. Car, who lives in city A, wants to travel to city B with his friends. She knows that each city has four airports, which are located on the four vertices of A rectangle. There is A straight high-speed railway between the two airports in the same city. The unit mileage price of the high-speed railway in the i city is Ti. There are routes between the airports in any two different cities, and the unit mileage price of all routes is t.
So how should Car arrange the route to city B to save money as much as possible? She found that this was not a simple problem, so she came to you for advice.
Find A tourist route from city A to city B. the departure and arrival airports in the city can be selected arbitrarily, requiring the least total cost.
2. Input format
The first line has four positive integers s, t, A, B.
S represents the number of cities, t represents the price per unit mileage of aircraft, and A and B are the serial numbers of cities A and B respectively, (1 < = A, B < = s).
There are 1, 2, and 2 in the city, and the price of the second is the integer of the first, Yi, and 2 in the city.
3. Output format
A positive integer representing the minimum cost, with one decimal place reserved.
4. Sample input
3 10 1 3
1 1 1 3 3 1 30
2 5 7 4 5 2 1
8 6 8 8 11 6 3
5. Sample output
47.6
6. Data scale
0 < S <= 100
#include <bits/stdc++.h>
using namespace std;
#define MAXN 405
#define INF 0x7f7f7f7f
int n, s, t;
double P, p[MAXN], tx[5], ty[5], x[MAXN], y[MAXN], pri[MAXN][MAXN], ans = INF;
double calc(int a, int b, int c) {
if (tx[a] == tx[b] && ty[b] == ty[c] || tx[c] == tx[b] && ty[a] == ty[b]) return -1;
return (ty[a] - ty[b])/(tx[a] - tx[b]) * (ty[b] - ty[c])/(tx[b] - tx[c]);
}
double getp(int a, int b) {
return sqrt((x[a] - x[b]) * (x[a] - x[b]) + (y[a] - y[b]) * (y[a] - y[b])) * (a / 4 == b / 4 ? p[a / 4] : P);
}
int main() {
cin >> n >> P >> s >> t;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= 3; j++)
cin >> tx[j] >> ty[j];
if (calc(1, 2, 3) == -1) {
tx[4] = tx[1] + tx[3] - tx[2];
ty[4] = ty[1] + ty[3] - ty[2];
}
else if (calc(2, 1, 3) == -1) {
tx[4] = tx[2] + tx[3] - tx[1];
ty[4] = ty[2] + ty[3] - ty[1];
}
else {
tx[4] = tx[1] + tx[2] - tx[3];
ty[4] = ty[1] + ty[2] - ty[3];
}
for (int j = 1; j <= 4; j++) {
int o = i * 4 + j - 5;
x[o] = tx[j], y[o] = ty[j];
} cin >> p[i - 1];
}
memset(pri, INF, sizeof(pri));
for (int i = 0; i < n * 4; i++)
for (int j = 0; j < n * 4; j++)
pri[i][j] = pri[j][i] = getp(i, j);
for (int i = 0; i < n * 4; i++)
for (int j = 0; j < n * 4; j++) {
if (i == j) continue;
for (int k = 0; k < n * 4; k++) {
if (j == k || i == k) continue;
pri[i][j] = pri[j][i] = min(pri[i][j], pri[i][k] + pri[j][k]);
}
}
for (int i = 1; i <= 4; i++)
for (int j = 1; j <= 4; j++)
ans = min(ans, pri[s * 4 + i - 5][t * 4 + j - 5]);
cout << fixed << setprecision(1) << ans;
return 0;
}