Submission #1772243

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
int main(){
  int n,m;
  int ans=(1<<30);
  vector<P>node[305];
  cin>>n>>m;
  for(int i=0;i<m;i++){
    int a,b;
    int cost;
    cin>>a>>b>>cost;
    node[a].push_back(P(b,cost));
    node[b].push_back(P(a,cost));
  }
  for(int j=1;j<=n;j++){
    int temp=0;
    int min_cost[305];
    int INF=(1<<27);
    for(int i=0;i<=n;i++){
      min_cost[i]=INF;
    }
    priority_queue<P,vector<P>,greater<P> >pq;
    pq.push(P(0,j));
    min_cost[j]=0;
    while(!pq.empty()){
      P now=pq.top();pq.pop();
      int cost=now.first;
      int pos=now.second;
      for(int i=0;i<node[pos].size();i++){
	int next=node[pos][i].first;
	int ncost=node[pos][i].second;
	if(cost+ncost<min_cost[next]){
	  min_cost[next]=cost+ncost;
	  pq.push(P(cost+ncost,next));
	}
      }
    }
    for(int i=1;i<=n;i++){
      if(temp<min_cost[i])temp=min_cost[i];
    }
    if(ans>temp)ans=temp;
  }
  cout<<ans<<endl;
  return(0);
}

Submission Info

Judge Result