# NOI 2387:Til the Cows Come Home

#### 题目

http://bailian.openjudge.cn/practice/2387/

#### 源码

``````//
//  2387.cpp
//  test
//
//  Created by bytedance on 2020/9/8.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#define inf 99999999
using namespace std;
struct Edge{
int from,to,dis;
Edge(int from,int to,int dis):from(from),to(to),dis(dis){};
bool operator < (const Edge &e) const{
return e.dis<dis;
}
};

int n, t;

int main(){
cin >> t >> n;
vector<vector<Edge>> edges(n+1,vector<Edge>());
priority_queue<Edge> q;
vector<int> d(n+1,inf);
vector<bool> done(n+1);
while(t--){
int a,b,c;
cin >> a>>b>>c;
Edge e(a,b,c);
edges[a].push_back(e);
Edge e2(b,a,c);
edges[b].push_back(e2);
}
//边读入ok，初始化距离数组
q.push(Edge(1,1,0));
d[1]=0;
while(!q.empty()){
int node  = q.top().to;q.pop();
if(done[node])continue;
done[node] = true;
for(int i = 0;i < edges[node].size();++i){
Edge e = edges[node][i];
if(d[e.to]>d[node]+e.dis){
d[e.to] = d[node]+e.dis;
q.push(Edge(1,e.to,d[e.to]));
}
}
}
cout << d[n];
return 0;
}
``````