存储
2025-10-07 14:46:03
发布于：浙江
18阅读
0回复
0点赞
题目描述
N(1≤N≤1000)头牛要去参加一场在编号为 x(1≤x≤N) 的牛的农场举行的派对。有 M(1≤M≤100000) 条有向道路，每条路长 T
i
(1≤T
i
≤100)；每头牛都必须参加完派对后回到家，每头牛都会选择最短路径。求这N 头牛的最短路径（一个来回）中最长的一条的长度。 特别提醒：可能有权值不同的重边。
提示
数据保证使用邻接矩阵存图不会超时
输入格式
第 1 行：3 个空格分开的整数 N,M,X；
第 2…M+1 行：3 个空格分开的整数 A
i
,B
i
,T
i
，表示有一条从 A
i
到 B
i
的路，长度为 T
i
。
输出格式
一行一个数，表示最长最短路的长度。
样例组输入#1
4 8 2
1 2 4
1 3 2
1 4 7
2 1 1
2 3 5
3 1 2
3 4 4
4 2 3
样例组输出#1
10
必做
小码君的太空基地spfa
题目描述
题目描述
公元2070年，人类在火星上建造的数个太空基地，太空基地的编号为 1 至 n，太空基地之间共有 m 条单向联通的道路，走每条路都会消耗小码君太空服中的氧气，幸运的是，太空基地之间有免费的泊船，不仅不消耗氧气，还可以回复氧气。问从 s 基地移动到 t 基地最少消耗多少氧气。
提示
1≤n,m≤5000
每条路径的距离不超过 1e9
输入格式
第一行四个由空格隔开的整数，分别表示 n，m，s，t;
之后的m行，每行三个正整数 x，y，z，表示一条从 x 到 y 长度为 z 的单向边，若 z>0 表示消耗氧气，若 z<0 表示可以搭船并恢复 −z 氧气。
输出格式
一个整数表示最少消耗的氧气，如果无法到终点，输出 1000000000
样例组输入#1
5 5 1 5
1 2 5
1 3 7
3 5 1
1 4 10
4 5 -4
样例组输出#1
6
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,m,x,z;
int mp[5010][5010];
int vis[10010],dis[10010];
void SPFA(int x){
memset(dis,0x3f,sizeof dis);
memset(vis,0,sizeof vis);
dis[x]=0;
vis[x]=1;
queue<int> a;
a.push(x);
while(a.size()){
int u=a.front();
a.pop();
vis[u]=0;
for(int i=1;i<=n;i++){
if(dis[i]>dis[u]+mp[u][i]){
dis[i]=dis[u]+mp[u][i];
if(!vis[i]){
vis[i]=1;
a.push(i);
}
}
}
}int m=0;
}
signed main(){
cin >> n >> m >> x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mp[i][j]=1e9;
}
}
for(int i=1;i<=m;i++){
int u,v,w;
cin >> u >> v >> w;
if(mp[u][v]==0)mp[u][v]=v;
else mp[u][v]=min(w,mp[u][v]);
}
int ans=-114514;
for(int i=1;i<=n;i++){
int sum=0;
if(i==x)continue;
SPFA(i);
sum+=dis[x];
SPFA(x);
sum+=dis[i];
ans=max(sum,ans);
}
cout << ans;
return 0;
}
有帮助，赞一个