Park View
Title Description
Xiao Ming likes watching scenery, so today he came to the park.
It is known that the park has ， N ， scenic spots, and there are ， M roads between scenic spots. Xiao Ming has ， Q sightseeing plans, and each plan includes a starting point ， st ， and an ending point ， ed, indicating that he wants to go from ， st ， to ， ed. But Xiao Ming's physical strength is limited. For each plan, he wants to take the least way to complete it. Can you help him?
Enter description
The first line of input contains three positive integers N,M,Q
Lines ＾ 2 ＾ to ＾ M + 1 ＾ each line contains three positive integers ＾ u,v,w represents ＾ U ↔ v # is the distance between two paths.
Lines ＾ M+2 ＾ to ＾ M + Q-1 ＾ each line contains two positive integers ＾ st,ed, whose meaning is described in the question.
(1 ≤ N ≤ 400，1 ≤ M ≤ N×(N−1)/2，Q ≤ 10^3，1 ≤ u,v,st,ed ≤ n，1 ≤ w ≤ 10^9)
Output description
The output is a total of # Q # rows, corresponding to the query in the input data.
If you cannot reach ， ed ， from ， st ， output - 1.
sample input
3 3 3 1 2 1 1 3 5 2 3 2 1 2 1 3 2 3
sample output
1 3 2
Reference code:
#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL; //The advantages of defining INF in this way are: INF < = INF + X
const int N = 405;
long long dp[N][N];
int n,m,q;
void input(){
//Two initialization methods
// for(int i = 1; i <= n; i++)
// for(int j = 1; j <= n; j++)
// dp[i][j] = INF;
memset(dp,0x3f,sizeof(dp));
for(int i = 1; i <= m; i++){
int u,v;long long w;
cin >> u >> v >> w;
dp[u][v]=dp[v][u] = min(dp[u][v] , w); //Prevent heavy edges
}
}
void floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
dp[i][j] = min(dp[i][j] , dp[i][k] + dp[k][j]);
}
void output(){
int s, t;
while(q--){
cin >> s >>t;
if(dp[s][t]==INF) cout << "-1" <<endl;
else if(s==t) cout << "0" <<endl; //If not, dp[i][i] is not equal to 0
else cout <<dp[s][t]<<endl;
}
}
int main(){
cin >> n >> m >> q;
input();
floyd();
output();
return 0;
}Print path
Title Description
There are N cities in the kingdom. There is a direct road or no road between any two cities. There is a toll on each road, and taxes must be paid after passing through each city. Define the cost from # a city to # b city, which is the sum of the path length plus the sum of the tolls of all cities except # a # and # b.
Given several pairs of cities, please print the path with the least cost between them. If more than one path matches, the path with the smallest dictionary order is output.
Enter description
The first line gives a N to indicate the number of cities. If N=0 indicates the end.
Next, there are # N # numbers in # N # line
，
Represents the direct toll from the # i # city to the # j # City, if= − 1 indicates that there is no direct route.
The next line has # N # numbers, and the # i # number represents the tax of # i # city. Then there are many lines. Each line has two numbers, indicating the starting point and destination city. If the two numbers are - 1, it ends.
Output description
For each given two cities, output the cheapest path through which points and the least cost.
sample input
3 0 2 -1 2 0 5 -1 5 0 1 2 3 1 3 2 3 -1 -1 0
sample output
From 1 to 3 : Path: 1-->2-->3 Total cost : 9 From 2 to 3 : Path: 2-->3 Total cost : 5
Reference code:
The path part is described as follows:
1. Definition of path. Record the path with path [] []. path[i][j] = u represents the shortest path with the starting point of I and the ending point of j. the next point starting from I is u. A complete path starts from s, checks path[s][j] = u, finds the next point u, then starts from u, checks path[u][j] = v, the next point is v, and so on, and finally reaches the end point j.
2. Calculation of path. Path [i] [J] = path [i] [k] calculates the next point from I. Because K is on the shortest path of i-j, i-k is also the shortest path. Compare path[i][j] and path[i][k], which both represent the next point from I, and this point is on the same path, so there is path[i][j] = path[i][k].
#include<bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
const int N = 505;
int n, mmap[N][N], tax[N], path[N][N];
void input(){
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
scanf("%d", &mmap[i][j]);
if(mmap[i][j] == -1) mmap[i][j] = INF;
path[i][j] = j; //path[i][j]: at this time, I and j are adjacent or disconnected
}
for(int i = 1; i <= n; i++) scanf("%d", &tax[i]); //tax
}
void floyd(){
for(int k = 1; k <= n; k++)
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++) {
int len = mmap[i][k] + mmap[k][j] + tax[k]; //Calculate the shortest path
if(mmap[i][j] > len) {
mmap[i][j] = len;
path[i][j] = path[i][k]; //Mark to the previous point of the point
}
else if(len == mmap[i][j] && path[i][j] > path[i][k])
path[i][j] = path[i][k]; //If the distance is the same, in dictionary order
}
}
void output(){
int s, t;
while(scanf("%d %d", &s, &t)) {
if(s == -1 && t == -1) break;
printf("From %d to %d :\n", s, t);
printf("Path: %d", s);
int k = s;
while(k != t) { //Output path from start to end
printf("-->%d", path[k][t]);
k = path[k][t]; //Step by step to the end
}
printf("\n");
printf("Total cost : %d\n\n", mmap[s][t]);
}
}
int main(){
scanf("%d", &n);
input();
floyd();
output();
return 0;
}Exponential movement
Title Description
A graph has # n # points and # m # edges connecting these points, and the side length is # 1 # km. Xiao Ming's mobility is very strange. He can run ， 2^t ， kilometers per second. T ， is any natural integer. Ask Xiao Ming how many seconds it will take at least from point # 1 # to point # n.
Enter description
In the first line, two integers, n, m, represent the number of points and edges.
Next, there are two numbers a and b in each line of # m # line, representing an edge from # a # to # b #.
(1 ≤ n ≤ 50, 1 ≤ m ≤ 10000, optimal path length ≤ 2 ^ 32.)
Output description
Output an integer representing the answer.
sample input
5 5 1 2 2 2 3 4 3 5 2 3
sample output
1
Reference code:
The path of this problem is "in circles", and some points can be passed many times.
The path Xiao Ming runs can be divided into several segments, each segment is 2^t long, so the key is to determine whether there is a 2^t path between any point pair (i, j). Because the path between all point pairs needs to be calculated, Floyd algorithm is appropriate. Calculate a new graph. If there is a path with a length of 2^t between point pairs (i, j), assign the side length mp[i][j] of (i, j) to 1 second, otherwise it is infinite. On this new graph, finding the shortest path from 1 to n is the answer.
Path with calculation length of 2^t: according to the principle of multiplication, 2^t = 2^{t-1} +2^{t-1}. Use p[i][j][t] = true to indicate that there is a path with a length of 2^t between I and j. according to the idea of Floyd algorithm, the path passes through a transit point K, with p[i][j][t]= p[i][k][t-1]+ p[k][j][t-1]. The complexity O(n^3) of the new graph mp [] is calculated by using the multiplication principle. Calculate the shortest path on the new graph mp [], and use any shortest path algorithm. Here, use the simplest Floyd algorithm.
#include<bits/stdc++.h>
using namespace std;
const int N = 55;
bool p[N][N][34];
int mp[N][N];
int main(){
memset(mp,0x3f,sizeof(mp));
int n,m; cin >> n >> m;
for( int i = 1;i <= m; i++){
int u,v; cin >> u >> v;
mp[u][v] = 1;
p[u][v][0] = true;
}
for(int t = 1;t <= 32; t++) //Path with length of 2^t
for(int k = 1;k <= n; k++) //Floyd
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
if(p[i][k][t - 1] == true && p[k][j][t - 1] == true){
p[i][j][t] = true;
mp[i][j] = 1; //The new graph is calculated
}
for(int k = 1;k <= n; k++) //For the shortest circuit, use Floyd
for(int i = 1;i <= n; i++)
for(int j = 1;j <= n; j++)
mp[i][j] = min(mp[i][j],mp[i][k] + mp[k][j]);
cout << mp[1][n] << endl;
return 0;
}If there are mistakes and areas that need to be improved, you are welcome to correct and give advice.