1126. Minimum cost
920. Best Ride
1126. Minimum cost
Among n people, some people’s bank accounts can transfer funds to each other.
The fees for transferring money between these people vary.
Given what percentage of the handling fee needs to be deducted from the transfer amount when transferring money between these people, please ask A
What is the minimum amount of money required so that B receives 100 yuan after the transfer.
Input format
The first line inputs two positive integers n and m, which respectively represent the total number of people and the logarithm of people who can transfer money to each other.
In the following m lines, each line inputs three positive integers x, y, z, which means that a transfer fee between the person labeled x and the person labeled y needs to be deducted by z% (z<100).
The last line inputs two positive integers A and B.
Data guarantees that funds can be transferred directly or indirectly between A and B.
Output format
Output the minimum total cost required by A to make B receive 100 yuan.
Accurate to 8 decimal places.
Data range
1≤n≤2000
m≤105
Input example:
3 3
1 2 1
2 3 2
1 3 3
1 3
Example output:
103.07153164
Difficulty: Easy
Time/space limit: 1s/64MB
Total number of passes: 10083
Total attempts: 21211
Source: “Informatics Olympiad Comprehensive Guide”
I found that you always like to copy the code. When the last part of the question is exactly the same as the previous one, it is really…
In this question there are
c
o
s
t
A
?
c
h
a
r
g
e
=
c
o
s
t
B
=
100
cost_A * charge = cost_B = 100
costAcharge=costB?=100
to let
c
o
s
t
A
cost_A
If costA? has a minimum, then charge is required to be maximum. In other words, this question can be regarded as finding the longest “distance”
Will
d
i
j
k
s
t
r
a
dijkstra
To apply the dijkstra algorithm to this question, you need to understand the essence of this algorithm. Why is it that the first time this point is retrieved (finding the point with the smallest distance each time), its distance must be the smallest?
(Notice
d
i
j
k
s
t
r
a
dijkstra
Dijkstra’s algorithm can only solve the case where the edge weights are non-negative)
This is because
d
i
j
k
s
t
r
a
dijkstra
The essence of Dijkstra’s algorithm is greedy; since it is ensured that each node is visited only once, and since the edge weight is non-negative, the shortest distance retrieved in each round is non-decreasing, so when it is retrieved for the first time, the distance between the point and the source The distance between points must be the smallest (the more you add, the bigger)
This question can be used
d
i
j
k
s
t
r
a
dijkstra
The reason for dijkstra’s method is also because greedy results can be obtained
Since the handling fee must be a direct number between 0 and 1, and this question does not use continuous addition but continuous multiplication to calculate the distance, the distance must be non-increasing, or in other words, decreasing;
At this time, greed can get the final result and can be used
d
i
j
k
s
t
r
a
dijkstra
dijkstra method
#include<bits/stdc + + .h>
using namespace std;
typedef pair<double,int> PDI;
const int N = 2010;
const int M = 200000;
bool vis[N];
int h[N], e[M], ne[M], idx;
double w[M], dis[N];
int n, m, st, ed;
void add(int a, int b, double c)
{<!-- -->
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx + + ;
}
//Pay attention to what kind of single-source "shortest path" model this question is
void dijkstra()
{<!-- -->
//Because it is the longest path, it is not needed at this time! Initialize the dis array to INF
//Due to seeking the maximum path, the longest distance in this question is 1, that is, there is no transit loss.
dis[st] = 1; //st * 1 = st;
priority_queue<PDI> heap;
heap.push({<!-- -->1, st});
while(!heap.empty()){<!-- --> //This question must use a heap, otherwise TLE will occur
int u = heap.top().second; heap.pop();
if(vis[u]) continue;
vis[u] = true;
if(u == ed) break;
for(int i = h[u]; i != -1; i = ne[i]){<!-- -->
int j = e[i];
dis[j] = max(dis[j], dis[u] * w[i]);
heap.push({<!-- -->dis[j], j});
}
}
}
int main()
{<!-- -->
memset(h, -1, sizeof h);
cin >> n >> m;
while(m --){<!-- -->
int a, b, c;
cin >> a >> b >> c;
double t = (100.0 - c) / 100;
add(a, b, t);
add(b, a, t);
}
cin >> st >> ed;
dijkstra();
double ans = 100.0 / dis[ed];
printf("%.8f", ans);
return 0;
}
This question can be passed without heap optimization, and the time is less than tens of milliseconds?
#include<bits/stdc + + .h>
using namespace std;
const int N = 2010;
int n, m;
int st, ed;
double g[N][N];
bool vis[N];
double dis[N]; //Used to record the total handling fee that needs to be deducted between two points
//Make sure to always decrement, so greedy is available
double dijkstra()
{<!-- -->
dis[st] = 1;
for(int i = 0;i < n;i + + ){<!-- -->
int u = -1;
for(int j = 1;j <= n;j + + ){<!-- -->
if(!vis[j] & amp; & amp; (u == -1 || dis[j] > dis[u])){<!-- -->
u = j;
}
}
if(u == ed) return dis[u];
vis[u] = 1;
for(int j = 1;j <= n;j + + ){<!-- -->
dis[j] = max(dis[j], dis[u] * g[u][j]);
}
}
return dis[ed];
}
int main()
{<!-- -->
cin >> n >> m;
while(m --){<!-- -->
int a, b, c;
scanf("%d%d%d", & amp;a, & amp;b, & amp;c);
double t = (100.0 - c) / 100;
g[a][b] = g[b][a] = max(t, g[a][b]);
}
cin >> st >> ed;
double charge = dijkstra();
double ans = 100 / charge;
printf("%.8f", ans);
return 0;
}6
920. Best ride
H City is a tourist attraction with thousands of people visiting every year.
For the convenience of tourists, bus companies have set up bus stations and opened some one-way bus routes at various tourist attractions, hotels, restaurants and other places.
Each one-way bus route starts from a certain bus station, passes through several bus stations in sequence, and finally reaches the final bus station.
A traveler recently traveled to City H. He really wanted to go to S Park. However, if there is no bus from his hotel to S Park directly, he may have to take a certain bus for a few stops and then get off and transfer. There is another bus at the same platform, and after several transfers, it reaches S Park.
Now use integers 1, 2,…N to number all the bus stops in H City. It is agreed that the bus stop number of the hotel where this passenger is located is 1, and the number of the S Park bus stop is N.
Write a program to help this passenger find an optimal ride plan that will minimize the number of transfers during the ride from the hotel to S Park.
Input format
There are two numbers M and N in the first line, indicating that M one-way bus lines have been opened, with a total of N stations.
From the second line to the M+1th line, the information of the 1st to the Mth bus lines is given in sequence, where the i+1th line gives the information of the i-th bus line. From left to right, press Run All station numbers on the line are given in sequence, with a space separating two adjacent station numbers.
Output format
There is one line in total. If it is impossible to reach S Park from the hotel by bus, output NO. Otherwise, output the minimum number of transfers. A transfer number of 0 means that you can get there without changing buses.
data range
1≤M≤100
2≤N≤500
Input example:
3 7
6 7
4 7 3 6
2 1 3 5
Example output:
2
Difficulty: Moderate
Time/space limit: 1s/64MB
Total number of passes: 9542
Total attempts: 17008
Source: NOI1997
I wrote for more than an hour and passed ten data, but I didn’t consider that it was a one-way trip… I don’t know if it would be possible if it was a round trip… Qianqian collapsed
#include<bits/stdc + + .h>
using namespace std;
const int N = 510;
const int M = 110;
int n, m;
bool flag[M][N]; //flag[i][j] indicates that the i-th vehicle can reach the j-th station (all points in the same row are at the same distance)
vector<int> v[N]; //Indicates which buses arrive at the i-th node
int dis[N];
bool vis[N], st[M];
void bfs()
{<!-- -->
memset(dis, -1, sizeof dis);
queue<int> q;
q.push(1);
while(!q.empty()){<!-- -->
int now = q.front(); q.pop();
int step = dis[now];
if(vis[now]) continue;
vis[now] = 1;
for(int i = 0;i < v[now].size();i + + ){<!-- -->
int bus = v[now][i];
if(st[bus]) continue; //Ensure that each bus is only accessed once
st[bus] = 1;
cout << "bus: " << bus << endl;
for(int j = 1;j <= n;j + + ){<!-- -->
if(flag[bus][j] & amp; & amp; dis[j] == -1){<!-- --> // Ensure that each dis is updated only once
dis[j] = step + 1;
if(j == n){<!-- -->
return;
}
q.push(j);
}
}
}
}
}
int main()
{<!-- -->
cin >> m >> n;
string input;
getline(cin, input);
for(int i = 1;i <= m;i + + ){<!-- -->
getline(cin, input);
stringstream ss;
ss << input;
int node;
while(ss >> node){<!-- -->
flag[i][node] = 1;
v[node].push_back(i);
}
}
//According to this definition, the distances of all points on the same bus are the same, which feels like changing from a point to a set of points.
//How to search, how to ensure that the distance is the smallest when each point is searched for the first time
bfs();
if(dis[n] == -1) puts("NO");
else cout << dis[n];
return 0;
}
Optimized code:
This question requires the number of transfers, and the number of transfers = the number of rides – 1;
Regarding the number of rides, convert the number of rides into a distance problem. The distance between stops on the same BUS is 1 (you can reach it by taking one bus)
So in
g
[
N
]
[
N
]
g[N][N]
The edge weight g[N][N] is stored in the array. Each stop of each bus and all the stops behind it have a directed edge with an edge weight of 1 (difficulty point) It is the transformation of this information, how to abstract the edge rights through the carrier of BUS)
//In fact, one-way cars and round-trip cars are the relationship between directed graphs and undirected graphs
//The difficulty in this question is what is distance?
//Actually, I have thought about it, but I have brushed it off, but I have not materialized the idea.
#include<bits/stdc + + .h>
using namespace std;
const int N = 510;
const int INF = 0x3f;
const int MAX = 0x3f3f3f3f;
int n, m;
int g[N][N];
int dis[N]; //Record the number of buses required to go from station 1 to other stations.
int stop[N]; //Record the stations where each bus stops in sequence. The same bus stops at the station. Each station after the previous point has a directed edge with an edge weight of 1, which means One-way reachable
//Because the distance is always 1, you can use BFS to search by layer
void bfs()
{<!-- -->
memset(dis, INF, sizeof dis);
dis[1] = 0;
queue<int> q;
q.push(1);
while(!q.empty()){<!-- -->
int now = q.front(); q.pop();
for(int i = 1;i <= n;i + + ){<!-- -->
//g[now][i] ensures that they are on a bus
if(g[now][i] & amp; & amp; dis[i] > dis[now] + 1){<!-- -->
dis[i] = dis[now] + 1;
q.push(i);
}
}
}
}
int main()
{<!-- -->
cin >> m >> n;
string input;
getline(cin, input);
while(m --){<!-- -->
getline(cin, input);
stringstream ss(input);
int cnt = 0, t;
while(ss >> t) stop[cnt + + ] = t;
for(int i = 0;i < cnt; i + + ){<!-- -->
for(int j = i + 1;j < cnt;j + + ){<!-- -->
g[stop[i]][stop[j]] = 1; //The edge weight from the I-th site to the J-th site is 1
}
}
}
//According to this definition, the distances of all points on the same bus are the same, which feels like changing from a point to a point set.
//How to search, how to ensure that the distance is the smallest when each point is searched for the first time
bfs();
if(dis[n] == MAX) puts("NO");
else cout << dis[n] - 1; //The number of transfers is equal to the number of rides - 1;
return 0;
}