Mapping method of single source shortest path
Heat Wave
Title Link: Heat Wave
Analysis: for a relatively naked problem, directly build a drawing and set a template, and I will directly use spfa water.
Code implementation:
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int N=2510,M=12410;
int n,m,str,ed;
int dist[N];
int h[N],e[M],ne[M],idx=1,w[M];//Chained forward star storage diagram
bool st[N];
queue<int> q;
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa(){
memset(dist,0x3f,sizeof dist);
dist[str]=0;
q.push(str);
st[str]=1;
while(q.size()){
auto t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]) q.push(j),st[j]=1;//It's also good to st[j] remove it here, but the efficiency will be lower
}
}
}
}
int main(){
cin>>n>>m>>str>>ed;
for(int i=1;i<=m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c);
add(b,a,c);
}
spfa();
cout<<dist[ed]<<endl;
return 0;
}
messenger
Title Link: messenger
Analysis: for this problem, we find that for each point except 1, the shortest time required for communication is the shortest path distance from 1 to this point, and the time for all points to complete communication is the maximum value of the shortest path from all points to 1 (except 1). Therefore, we only need the shortest path from 1 to all points (except 1).
Code implementation:
#include<iostream>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int n,m;
const int N=110;
int g[N][N];
int main(){
cin>>n>>m;
memset(g,0x3f,sizeof g);
//Here, we do not need to initialize g[i][i] to 0, so it will not be used when updating, and it is also right not to use this state when updating
while(m--){
int a,b,c;
cin>>a>>b>>c;
g[a][b]=g[b][a]=min(g[a][b],c);//Prevent multiple edges
}
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
g[i][j]=min(g[i][j],g[i][k]+g[k][j]);
int res=0;
for(int i=2;i<=n;i++)//Note that starting from 2 will cause an error if starting from 1 because we did not initialize g[1][1] to 0
if(g[1][i]==INF) {
res=-1;
break;
}
else res=max(res,g[1][i]);
cout<<res;
return 0;
}
Sweet butter
Title Link: Sweet butter
Analysis: for this problem, we can enumerate the sugar in each pasture, then find the shortest path from this pasture to all other pastures, and then enumerate the pasture where each cow is located, find these distances and take the smallest one. If you go directly to dijkstra, you may time out. Here we use spfa. The person who wrote the question didn't have a card spfa.
Code implementation:
#include<iostream>
#include<queue>
#include<cstring>
using namespace std;
const int INF=0x3f3f3f3f;
int s,n,m,tmp;
const int N=810,M=2910;
int res=INF;
int id[N],e[M],ne[M],idx=1,h[N],w[M];
bool st[N];
int dist[N];
queue<int> q;
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int spfa(int str){
memset(dist,0x3f,sizeof dist);
q.push(str);
st[str]=1;
dist[str]=0;
while(q.size()){
auto t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[t]+w[i]){
dist[j]=dist[t]+w[i];
if(!st[j]) q.push(j),st[j]=1;
}
}
}
int ans=0;
for(int i=1;i<=s;i++)
if(dist[id[i]]==INF) return INF;//Once two pastures are disconnected, return to INF directly
else ans+=dist[id[i]];
return ans;
}
int main(){
cin>>s>>n>>m;
for(int i=1;i<=s;i++) cin>>id[i];//Record the pasture where each cow is located
while(m--){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
for(int i=1;i<=n;i++) res=min(res,spfa(i));
cout<<res<<endl;
return 0;
}
Minimum cost
Title Link: Minimum cost
Analysis: we will explain an interesting problem with spfa and dijkstra respectively.
Let's first consider that the amount of money at point A is SA, and the remaining money after passing through each point is times the original Ci. After passing through all points to B, there is an equation SA * C1 * C2 * C3= 100. When we require the minimum value of SA, we require the maximum value of the product of that pile of C. Because Ci is greater than 0 and less than or equal to 1, the more multiplied, the smaller. Next, we discuss two methods.
spfa: spfa is based on its relaxation operation. For a starting point, if we can update the adjacent points through its edge (all points are initially initialized to 0 and the starting point is initialized to 1), that is, if the product of C becomes smaller, we can operate and add this point to the queue. Therefore, spfa can find the shortest and longest path.
Code implementation:
#include<iostream>
#include<queue>
using namespace std;
int n,m,A,B;
const int N=2010,M=2e5+10;
int e[M],ne[M],idx=1,h[N];
double w[M];
double dist[N];
bool st[N];
queue<int> q;
void add(int a,int b,double c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void spfa(){
dist[B]=1;
st[B]=1;
q.push(B);
while(q.size()){
auto t=q.front();
q.pop();
st[t]=0;
for(int i=h[t];i;i=ne[i]){
int j=e[i];
if(dist[j]<dist[t]*w[i]){
dist[j]=dist[t]*w[i];
if(!st[j]) q.push(j),st[j]=1;
}
}
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
double c=(100.0-z)/100;//Into c in our analysis
add(x,y,c);
add(y,x,c);
}
cin>>A>>B;
spfa();//Take B as the starting point
printf("%.8lf",100/dist[A]);
return 0;
}
dijkstra: we know that dijkstra is based on greedy thinking. For the shortest path problem, we first find the shortest one from the end point, which is itself at the beginning, and then use it to update other points, but it can't find the longest path problem (I won't prove it here, which should be in the introduction to algorithms). For C, which requires the most, Every time we find the largest C to update, it is also itself at the beginning, and then update it in a similar way. We find that it can also update AC. (I have a guess here that dijkstra can't find the longest way because it's not the end itself that is closest to the end at the beginning.) It proves that I really won't. I'm too good, leaving tears of frustration.
Code implementation: (I don't want to write any more, so I just paste y general)
#include <iostream>
using namespace std;
const int N = 2010;
int n, m, S, T;
double g[N][N];
double dist[N];
bool st[N];
void dijkstra(){
dist[S] = 1;//The starting point is initialized to 1, and other points are 0
for (int i = 1; i <= n; i ++ ){
int t = -1;
//Find the largest C
for (int j = 1; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] < dist[j]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++ )
dist[j] = max(dist[j], dist[t] * g[t][j]);//to update
}
}
int main(){
scanf("%d%d", &n, &m);
while (m -- ){
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
double z = (100.0 - c) / 100;//Into C in our analysis
g[a][b] = g[b][a] = max(g[a][b], z);
}
cin >> S >> T;
dijkstra();
printf("%.8lf\n", 100 / dist[T]);
return 0;
}
Incidentally, for this question, dijkstra: about 570ms, spfa: about 242ms.
Optimal ride
Title Link: Optimal ride
Analysis: there are some skills in drawing this problem. First of all, there must be many solutions to this problem (I guess). Since we are the single source shortest path practice, let's use the single source shortest path method to solve it. For each route, the distance from the front point to any point behind is set to 1, and then we find the shortest path from the starting point to the end point, and then subtract 1 is the answer (because it is transferred on the same route once). However, there is another special case. When the starting point and the end point coincide, the shortest path is 0, and subtracting 1 is - 1, So we have to deal with it in a special way.
Code implementation:
//Shit, how do you feel that the bfs I wrote is spfa
#include<iostream>
#include<sstream>
#include<queue>
#include<cstring>
using namespace std;
int n,m,tmp;
const int N=510,M=25010,INF=0x3f3f3f3f;
int e[M],ne[M],idx=1,h[N];
int stop[N];
int dist[N];
queue<int> q;
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
void bfs(){
memset(dist,0x3f,sizeof dist);
dist[1]=0;
q.push(1);
while(q.size()){
auto t=q.front();
q.pop();
for(int i=h[t];i;i=ne[i]){
int j=e[i];
if(dist[j]==INF){//Because it is bfs, it must be the minimum value when updating for the first time
dist[j]=dist[t]+1;
q.push(j);
}
}
}
}
int main(){
string s;
cin>>m>>n;
getline(cin,s);//Spit out \ n because cin will not read the end of \ 0
for(int i=1;i<=m;i++){
getline(cin,s);
stringstream ss(s);//Save se into ss
int cnt=0;
while(ss>>tmp) stop[cnt++]=tmp;//Read numbers into tmp
for(int j=0;j<cnt;j++)
for(int k=j+1;k<cnt;k++)
add(stop[j],stop[k]);//Add edge
}
bfs();//Because the direct weight is bfs
if(dist[n]==INF) puts("NO");//unsolvable
else cout<<max(dist[n]-1,0)<<endl;
return 0;
}
Expensive bride price
Title Link: Expensive bride price
Analysis: the most interesting question! I was dizzy when I read the questions. Come on. The most difficult thing is to consider how to build a map, which is easy. I have to say that the drawing method of this problem is really awesome... We artificially design a virtual starting point. The distance from it to all items is the price of these items, and then connect the items that can be replaced equivalently at the cost of the gold coins required after replacement. Then this problem becomes a shortest path problem. The starting point is the virtual starting point and the end point is 1, but there is another constraint in this problem, that is, the grade difference, We enumerate all possible grade ranges, and then update only the points that meet the grade requirements while seeking the shortest circuit. So far, this problem is perfectly solved!
Code implementation:
We found that as long as we can build a map, we can write whatever we want in the back!
This is the heap optimization dijkstra I wrote: 117ms, probably because there are many sides
#include<iostream>
#include<queue>
#include<cstring>
#define x first
#define y second
using namespace std;
typedef pair<int,int> PII;
const int N=110,M=1e4+10,INF=0x3f3f3f3f;
int e[M],ne[M],idx,h[N],w[M],level[N];
int m,n,res=INF;
int dist[N];
bool st[N];
void add(int a,int b,int c){
e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
int dijkstra(int left){
priority_queue<PII,vector<PII>,greater<PII>> heap;
memset(st,0,sizeof st);
memset(dist,0x3f,sizeof dist);
dist[0]=0;
heap.push({0,0});
//At the beginning, the sentence st[0]=1 was added. As a result, it was adjusted for a long time and I was so angry
while(heap.size()){
auto t=heap.top();
heap.pop();
int tmp=t.second;
if(st[tmp])continue;
st[tmp]=1;
for(int i=h[tmp];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[tmp]+w[i]&&level[j]>=left&&level[j]<=left+m){//The grade can only be updated if it meets the requirements
dist[j]=dist[tmp]+w[i];
heap.push({dist[j],j});
}
}
}
return dist[1];
}
int main(){
memset(h,-1,sizeof h);
cin>>m>>n;
for(int i=1;i<=n;i++){
int p,x;
cin>>p>>level[i]>>x;
add(0,i,p);
while(x--){
int t,v;
cin>>t>>v;
add(t,i,v);
}
}
for(int i=level[1]-m;i<=level[1];i++)//Enumerate the left boundary of the grade interval. The right boundary is the left boundary + M. here, because the grade difference between the two sides of the indirect transaction cannot exceed m, the length of the grade interval is m
res=min(res,dijkstra(i));
cout<<res<<endl;
return 0;
}
This is y the total simplicity dijkstra: 72ms
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110, INF = 0x3f3f3f3f;
int n, m;
int w[N][N], level[N];
int dist[N];
bool st[N];
int dijkstra(int down, int up){
memset(dist, 0x3f, sizeof dist);
memset(st, 0, sizeof st);
dist[0] = 0;
for (int i = 1; i <= n + 1; i ++ ){
int t = -1;
for (int j = 0; j <= n; j ++ )
if (!st[j] && (t == -1 || dist[t] > dist[j]))
t = j;
st[t] = true;
for (int j = 1; j <= n; j ++ )
if (level[j] >= down && level[j] <= up)
dist[j] = min(dist[j], dist[t] + w[t][j]);
}
return dist[1];
}
int main(){
cin >> m >> n;
memset(w, 0x3f, sizeof w);
for (int i = 1; i <= n; i ++ ) w[i][i] = 0;
for (int i = 1; i <= n; i ++ ){
int price, cnt;
cin >> price >> level[i] >> cnt;
w[0][i] = min(price, w[0][i]);
while (cnt -- ){
int id, cost;
cin >> id >> cost;
w[id][i] = min(w[id][i], cost);
}
}
int res = INF;
for (int i = level[1] - m; i <= level[1]; i ++ ) res = min(res, dijkstra(i, i + m));
cout << res << endl;
return 0;
}