POJ 2387 Til the Cows Come Home （dijkstra模板题）

Description

Bessie is out in the field and wants to get back to the barn to get as much sleep as possible before Farmer John wakes her for the morning milking. Bessie needs her beauty sleep, so she wants to get back as quickly as possible.

Farmer John's field has N (2 <= N <= 1000) landmarks in
it, uniquely numbered 1..N. Landmark 1 is the barn; the apple tree
grove in which Bessie stands all day is landmark N. Cows travel in the
field using T (1 <= T <= 2000) bidirectional cow-trails of various
lengths between the landmarks. Bessie is not confident of her
navigation ability, so she always stays on a trail from its start to its
end once she starts it.

Given the trails between the landmarks, determine the minimum
distance Bessie must walk to get back to the barn. It is guaranteed
that some such route exists.

Input

* Line 1: Two integers: T and N

* Lines 2..T+1: Each line describes a trail as three
space-separated integers. The first two integers are the landmarks
between which the trail travels. The third integer is the length of the
trail, range 1..100.

Output

* Line 1: A single integer, the minimum distance that Bessie must travel to get from landmark N to landmark 1.

Sample Input

Sample Output

90

理解dijkstra，对于所有未标号的点中选取一个d[x]最小的点，记为点x。将x标记
对于所有x出发的边(x,y)，更新d[y]=min(d[y],d[x]+mapp[x][y])
其实本质上是一个用优先队列优化的bfs（优先访问最短边的终点），在bfs中加上松弛操作就行了，同时保证访问过的点集之间的最短路是知道的
每次访问一个没有访问过的新点时，我们是要把它加入访问过的点集中去的对吧！加入的前提就是它与和它相连的访问过的所有点
做一次松弛操作，更新下状态。那么与它相邻但是没有访问过的点，我们加入优先队列。
代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <queue>

 #include <algorithm>

 #include <vector>

 using namespace std;

 #define inf 0x3f3f3f3f

 const int maxn =;

 vector <int>G[maxn];//存每个点连的边的编号

 bool done[maxn];//标记某点是否访问过

 int p[maxn];//最短路中某个点的上一条路是几号

 int d[maxn];//原点到某点的距离

 int t,n;

 struct Edge{    //边

     int from,to,dis;

     Edge(int u,int v,int d):from(u),to(v),dis(d){}

 };

 vector <Edge>edges;

 struct HeapNode {//堆点，用于优化

     int d,u;

     bool operator <(const HeapNode& x) const {//优先考虑距离最小

         return d>x.d;

     }

 };

 void addEdge(int u,int v,int dis){//加边函数

     edges.push_back(Edge(u,v,dis));

     int m=edges.size();

     G[u].push_back(m-);

 }

 void dijkstra (int s) {

     priority_queue<HeapNode> q;

     memset(d,inf,sizeof d);

     d[s]=;

     memset(done,false,sizeof done);

     q.push(HeapNode{,s});

     while (!q.empty()){

         HeapNode x=q.top();

         q.pop();

         int u=x.u;

         if (done[u])

             continue;

         done[u]=true;

         for (int i=;i<G[u].size();++i){

             Edge& e=edges[G[u][i]];

             if (d[e.to]>d[u]+e.dis){//当e.to这个点是done过的点时，功能是得到

                 d[e.to]=d[u]+e.dis;

                 p[e.to]=G[u][i];

                 q.push((HeapNode){d[e.to],e.to});

             }

         }

     }

 }

 void init(){

     for (int i=;i<n;++i)

     G[i].clear();

     edges.clear();

 }

 int main()

 {

     //freopen("de.txt","r",stdin);

     while (~scanf("%d%d",&t,&n)){

         init();

         for (int i=;i<t;++i){

             int x,y,z;

             scanf("%d%d%d",&x,&y,&z);

             addEdge(x,y,z);

             addEdge(y,x,z);

         }

         dijkstra();

         printf("%d\n",d[n]);

     }

     return ;

 }

巴特西

POJ 2387 Til the Cows Come Home （dijkstra模板题）

最新文章

热门文章