Submission #202468

---

Source Code Expand

#include<stdio.h>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
#include<string>
#include<cmath>

#define REP(i,n) for(unsigned int i=0;i<n;i++)
#define INF 1<<31
#define SORT(A) sort(A.begin(),A.end())

using namespace std;

int main(){
	int N,M,ans=1e+7;
	cin>>N>>M;
	vector<vector<pair<int,int> > > g(N+1);
	REP(i,M){
		int a,b,t;
		cin>>a>>b>>t;
		g[a].push_back(pair<int,int>(b,t));
		g[b].push_back(pair<int,int>(a,t));
	}

	for(int i=1;i<=N;i++){
	//	cout<<"start is "<<i<<endl;
		priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
		vector<int>v(N+1,1e+7);
		q.push(pair<int,int>(0,i));
		v[i]=0;
		int maxim=0;
		while(!q.empty()){
			pair<int,int>now=q.top();
			q.pop();
		//	cout<<now.second<<endl;
			REP(j,g[now.second].size()){
				if(v[g[now.second][j].first]>now.first+g[now.second][j].second){
					v[g[now.second][j].first]=now.first+g[now.second][j].second;

					q.push(pair<int,int>(v[g[now.second][j].first],g[now.second][j].first));
				}
			}
		}
		for(int j=1;j<=N;j++)maxim=max(maxim,v[j]);
	//	REP(i,N+1)cout<<v[i]<<" ";cout<<"   "<<maxim<<endl;
		ans=min(ans,maxim);
	}
	cout<<ans<<endl;
	return 0;
}

Submission Info

Judge Result