Submission #1772200

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P; //first=cost,second=node_num
#define F first
#define S second
int main(){
  int n,m;
  vector<P>graph[303];
  int min_cost[303];
  priority_queue<P,vector<P>,greater<P> >p_que;

  int a,b;
  int cost,pos;
  int INF=1<<27;

  P bad_node=P(0,0);
  int minv=INF;
  
  int ans;
  
  cin >> n >> m;

  for(int i=0;i<=n;i++)
    min_cost[i]=INF;

  for(int i=0;i<m;i++){
    cin >> a >> b >> cost;
    graph[a].push_back(P(cost,b));
    graph[b].push_back(P(cost,a));
  }
  

  for(int cnt=1;cnt<=n;cnt++){

    p_que.push(P(0,cnt));

    for(int j=0;j<=n;j++)
      min_cost[j]=INF;
    min_cost[cnt]=0;
    bad_node=P(0,0);
    
    while(!p_que.empty()){
      P now=p_que.top();
      p_que.pop();
      cost=now.F;
      pos=now.S;
      for(int i=0;i<graph[pos].size();i++){
	int next=graph[pos][i].S;
	int ncost=graph[pos][i].F+cost;
	if(ncost<min_cost[next]){
	  min_cost[next]=ncost;
	  p_que.push(P(min_cost[next],next));
	}
      }
    }
    
    for(int i=1;i<=n;i++){
      if(bad_node.F<min_cost[i])
	bad_node=P(min_cost[i],i);
    }
    minv=min(minv,bad_node.F);
  }
  
  
  cout << minv << endl;
  return 0;
}

Submission Info

Judge Result