【 POJ - 2387 】Til the Cows Come Home （牛回家） dijkstra+优先队列

题目链接

代码：

#include <iostream> #include <algorithm> #include <queue> #include <vector> using namespace std; typedef long long ll; const int inf=1<<27; //无限远 也可以用100000000之类的 const int maxn=1010; struct node{ int v,w; node(int a,int b){v=a;w=b;} friend bool operator<(node a,node b){ //从小到大 return a.w>b.w; } }; int t,n,a,b,w,dis[maxn]; priority_queue<node> q; vector<node> g[maxn]; //邻接表 bool vis[maxn]={false}; //是否访问过 void dijk() //dijkstra { fill(dis,dis+maxn,inf); //初始化路径 到不了(无限远) dis[1]=0; //1到1的距离是0 q.push(node(1,0)); //加入起始点 while(!q.empty()) { int u=q.top().v; q.pop(); if(vis[u]) continue; //访问过 就跳过当前循环 vis[u]=1; for(int i=0;i<g[u].size();i++) { int v=g[u][i].v; int w=g[u][i].w; if(!vis[v]) { dis[v]=min(dis[v],dis[u]+w); q.push(node(v,dis[v])); } } } } int main() { cin>>t>>n; while(t--) { cin>>a>>b>>w; g[a].push_back(node(b,w)); //无向图 g[b].push_back(node(a,w)); } dijk(); cout<<dis[n]; ///N到1的距离 return 0; }