Submission #1772313

---

Source Code Expand

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;
#define INF 1<<27;
typedef pair<int,int>P;
int min_cost[100005];
vector<P>node[100005];
int main(){
  int n,m,ans=INF;
  cin>>n>>m;
  for(int i=1;i<=m;++i){
    int a,b,cost;
    cin>>a>>b>>cost;
    node[a].push_back(P(b,cost));
    node[b].push_back(P(a,cost));
  }
  priority_queue<P,vector<P>,greater<P> >pq;
  for(int i=1;i<=n;++i){
    fill(min_cost, min_cost+100005,1<<27);
    min_cost[i]=0;
    pq.push(P(0,i));
    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));
	}
      }
    }
    sort(min_cost+1,min_cost+n+1,greater<int>());
    if(ans>min_cost[1]) ans=min_cost[1];
  }
  cout<<ans<<endl;
  return 0;
}

Submission Info

Judge Result