BJFU_数据结构习题_283最长的最短路径的求解

妖狐艹你老母 2023-05-29 03:24 86阅读 0赞

欢迎登录北京林业大学OJ系统  
[http://www.bjfuacm.com][http_www.bjfuacm.com]

### 283最长的最短路径的求解 ###

**描述**  
设计一个算法，求图G中距离顶点v的最短路径长度最大的一个顶点。  
**输入**  
多组数据，每组数据m+2行。每组数据第一行为两个整数n和m，代表有n个顶点m条路。顶点编号为1到n。第二行到第m+1行每行有三个整数a，b和c，代表顶点a和顶点b之间有一条长度为c的路。第m+2有一个整数v，代表顶点v。当n和m都等于0时，输入结束。  
**输出**  
每组数据输出两行。第一行为最短路径最长的顶点编号c，第二行为两点的最短距离d。  
**输入样例 1**  
4 4  
1 2 1  
2 3 1  
3 4 1  
2 4 1  
4  
4 3  
1 2 3  
2 3 2  
2 4 6  
3  
0 0  
**输出样例 1**  
1  
2  
4  
8

#include<iostream>
    using namespace std;
    #define maxn 200
    #define inf 1e9
    int n;
    int e[maxn][maxn];
    int dis[maxn];
    int visit[maxn];
    void Dijkstra(int s)
    {
        
    	int min,k;
    	for(int i=1; i<=n; i++)
    	{
        
    		dis[i]=e[s][i];
    		visit[i]=0;
    	}
    	dis[s]=0;
    	visit[s]=1;
    	for(int i=0; i<n-1; i++)
    	{
        
    		min=inf;
    		for(int i=1; i<=n; i++)
    		{
        
    			if(!visit[i] && dis[i]<min)
    			{
        
    				min=dis[i];
    				k=i;
    			}
    		}
    		visit[k]=1;
    		for(int i=1; i<=n; i++)
    		{
        
    			if(!visit[i] && dis[i]>dis[k]+e[k][i])
    				dis[i]=dis[k]+e[k][i];
    		}
    	}
    }
    int main()
    {
        
    	int m,s;
    	int x,y,d;
    	while(cin>>n>>m&&n!=0&&m!=0)
    	{
        
    		for(int i=1; i<=n; i++)
    			for(int j=1; j<=n; j++)
    				e[i][j]=inf;
    		while(m--)
    		{
        
    			scanf("%d %d %d",&x,&y,&d);
    			e[x][y]=e[y][x]=d;
    		}
    		cin>>s;
    		Dijkstra(s);
    		int ans,max=-1;
    		for(int i=1; i<=n; i++)
    		{
        
    			if(dis[i]>max && dis[i]<inf)
    			{
        
    				max=dis[i];
    				ans=i;
    			}
    		}
    		cout<<ans<<endl<<max<<endl;
    	}
    	return 0;
    }

[http_www.bjfuacm.com]: http://www.bjfuacm.com