Submission #1772270

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>P;
vector<P>node[301];
int n,m,key;
int min_cost[301];
int INF=1<<27;
int maxv[301];
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  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 z=1;z<=n;z++){
    for(int i=1;i<=n;i++){min_cost[i]=INF;}
    min_cost[z]=0;
    priority_queue<P,vector<P>,greater<P> >pq;
    pq.push(P(0,z));
    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));
	  key=next;
	}
      }
    }
    sort(min_cost,min_cost+n);
    maxv[z]=min_cost[n-1];
  }
  sort(maxv,maxv+n);
  cout << maxv[n-1] << endl;
  return 0;
}

Submission Info

Judge Result