求助
查看原帖
求助
1100077
jg001楼主2024/11/30 22:55

10pts,求助!

#include<bits/stdc++.h>
using namespace std;

struct node{
	int to,w;
};
int n,m,x,y,z,r;
int temp[1005]={0};
int dist[1005],flag[1005];
vector<node> V[1005]; 
void Dijkstra(int s,int w){
	dist[s]=0;
	for(int i=1;i<=n;i++){ 
		int u=0;
		for(int j=1;j<=n;j++){
			if(dist[j]<dist[u]&&flag[j]==0)u=j;
		}
		flag[u]=1;
		for(int j=0;j<V[u].size();j++){
			int v=V[u][j].to;
			if(dist[v]>dist[u]+V[u][j].w) dist[v]=dist[u]+V[u][j].w;
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		temp[i]+=dist[i];
     }
	if(w==2)
	{
		int max1=0; 
		for(int i=1;i<=n;i++)
		{
			max1=max(max1,temp[i]);   
		}
		cout<<max1;
	}
}
int main(){ 
	memset(dist,0x3f,sizeof(dist));
	memset(flag,0,sizeof(flag));
	cin>>n>>m>>r;
	for(int i=1;i<=m;i++){
		cin>>x>>y>>z;
		V[x].push_back(node{y,z});
	}
	
    Dijkstra(r,1);
	memset(dist,0x3f,sizeof(dist));
	memset(flag,0,sizeof(flag));
	
    for(int i=1;i<=m;i++){
        V[y].push_back(node{x,z});
    }
    
    Dijkstra(r,2); 
   
	return 0;
}
2024/11/30 22:55
加载中...