复兴提高DAY09最短路（二）
2025-08-02 20:34:58
发布于：上海
0阅读
0回复
0点赞
T1小码君的太空基地
#include<bits/stdc++.h>
using namespace std;
struct node{
int from , to,len;
}a[10010];
int n , m , w , x , y,z , s , t;
int d[10010] ;
int main(){
scanf("%d %d %d %d",&n,&m,&s,&t);
for(int i = 1;i <= n;i++){
d[i] = 1e9;
}
d[s] = 0;
for(int i = 1;i <= m;i++){
cin>>a[i].from>>a[i].to>>a[i].len;
}
int from , to , len;
for(int k = 1;k < n;k++){
for(int i = 1;i <= m;i++){
from = a[i].from,to=a[i].to,len = a[i].len;
//判断走到to这个点能否更新最短距离
d[to] = min(d[to], d[from] + len);
}
}
//输出走到t的最少消耗氧气
cout << d[t];
return 0;
}
T2小码君的太空基地2
#include <bits/stdc++.h>
using namespace std;
struct node {
int u, v, w;
}t[1005];
int n, m, w;
int dis[505];
int cnt[505];
int main(){
cin >> n >> m >> w;
for(int i = 1; i <= m; i++){
cin >> t[i].u >> t[i].v >>t[i].w;
}
for(int i = m + 1; i <= m + w; i++){
cin >> t[i].u >> t[i].v >>t[i].w;
t[i].w *= -1;
}
for(int i = 1; i <= n; i++) dis[i] = 1e9, cnt[i] = 0;
dis[1] = 0;
bool f = 0;
while(!f){
int num = 0;
for(int i = 1; i <= m + w; i++){
int u = t[i].u, v = t[i].v, z = t[i].w;
if(dis[v] > dis[u] + z){
num ++;
dis[v] = dis[u] + z;
cnt[v]++;
if(cnt[v] > n) f = 1;
}
}
if(!num) break;
}
if(f) cout << "YES";
else cout << "NO";
return 0;
}
T3海盗宝藏
#include<bits/stdc++.h>
using namespace std;
int n,m,ans=0;//计数器
int dis[101][101],a[10001];//距离数组及必经之路数组
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d",&a[i]);//输入必经之路
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
scanf("%d",&dis[i][j]);//输入距离
}
}
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][k]+dis[k][j],dis[i][j]);
}
}
}
for(int i=2;i<=m;i++){
//计数
ans+=dis[a[i-1]][a[i]];
}
printf("%d",ans);
return 0;
}
T4搬家方案
#include<bits/stdc++.h>
using namespace std;
int g[105][105];
int main(){
int n,m;
cin>>n>>m;
memset(g,0x3f,sizeof g);
for(int i=1;i<=n;i++){
g[i][i]=0;
}
for(int i=1;i<=m;i++){
int x,y,z;
cin>>x>>y>>z;
g[x][y]=g[y][x]=min(g[x][y],z);
}
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]);
}
}
}
cout<<g[1][n];
return 0;
}
T5最短距离查询
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x,y,z,a,b;
int d[205][205];
int main(){
cin>>n>>m>>k;
memset(d,0x3f,sizeof d);//把d数组设置成无穷大 四个字节 3f3f3f3f
for(int i=1;i<=n;i++){
d[i][i]=0;
}
for(int i=1;i<=m;i++){
cin>>x>>y>>z;//x---->y距离为z的边
d[x][y]=z;
}
//floyed
for(int k=1;k<=n;k++){ //中间点 中转点
for(int i=1;i<=n;i++){ //起点
for(int j=1;j<=n;j++){ //终点
if(d[i][k]+d[k][j]<d[i][j]){
d[i][j]=d[i][k]+d[k][j];
}
}
}
}
for(int i=1;i<=k;i++){
cin>>a>>b;
if(d[a][b]==0x3f3f3f3f) cout<<"impossible"<<endl;
else cout<<d[a][b]<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个