[最短路Floyd]，启动！！！

B3647 【模板】Floyd

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 405;
int n,m;
int dis[N][N];
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}}}
}
int main()
{IOS;cin>>n>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = 1e9;if(i==j) dis[i][j] = 0;}}while(m--){int a,b,w;cin>>a>>b>>w;dis[a][b] = min(dis[a][b],w);dis[b][a] = min(dis[b][a],w);//双向边}floyd(); for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){cout<<dis[i][j]<<" ";}cout<<"\n";}
}

P1744 采购特价商品

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 300;
int n,m;
double dis[300][300];
struct Node{int x;int y;
}va[N];
void flyod()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}}}
}
int main()
{
//	IOS;cin>>n;for(int i=1;i<=n;i++) cin>>va[i].x>>va[i].y;cin>>m;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = 1e9;if(i==j) dis[i][j] = 0;}}for(int i=1;i<=m;i++){int a,b;cin>>a>>b;double w = sqrt( (va[a].x-va[b].x)*(va[a].x-va[b].x)+(va[a].y-va[b].y)*(va[a].y-va[b].y) );dis[a][b] = min(dis[a][b],w);dis[b][a] = min(dis[b][a],w);}flyod();int s,t;cin>>s>>t;printf("%.2lf",dis[s][t]);
}

P2888 [USACO07NOV] Cow Hurdles S

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 400;
int n,m,T;
int dis[N][N];
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = min(dis[i][j],max(dis[i][k],dis[k][j]));}}}
}
int main()
{IOS;cin>>n>>m>>T;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = 1e9;if(i==j) dis[i][j] = 0;}	}while(m--){int a,b,w;cin>>a>>b>>w;dis[a][b] = min(dis[a][b],w);}floyd();while(T--){int a,b;cin>>a>>b;if(dis[a][b]==1e9) cout<<-1<<"\n";else cout<<dis[a][b]<<"\n";}
}

P1364 医院设置

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 200;
int n;
int dis[N][N];
int va[N];
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}}}
}
int main()
{IOS;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = 1e9; if(i==j) dis[i][j] =0;}}for(int i=1;i<=n;i++){int a,b;cin>>va[i]>>a>>b;if(b!=0) dis[i][b] = min(dis[i][b],1),dis[b][i] =min(dis[b][i],1);if(a!=0) dis[i][a] = min(dis[i][a],1),dis[a][i] = min(dis[a][i],1);}floyd();int minn =1e9;for(int i=1;i<=n;i++){int sum = 0;for(int j=1;j<=n;j++){sum += dis[i][j]*va[j];}minn = min(sum,minn);}cout<<minn;
}

P1359 租用游艇

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
#define PII pair<int,int >
#define IOS ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
const int N = 400;
int n,m;
int dis[N][N];
void floyd()
{for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = min(dis[i][j],dis[i][k]+dis[k][j]);}}}
}
int main()
{IOS;cin>>n;for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j] = 1e9;if(i==j) dis[i][j] = 0;}}for(int i=1;i<=n-1;i++){for(int j=i+1;j<=n;j++){int w;cin>>w;dis[i][j] = min(dis[i][j],w);}}floyd();cout<<dis[1][n];
}