Til the Cows Come Home （求图中的最短路）

Til the Cows Come Home

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
  5 5
  1 2 20
  2 3 30
  3 4 20
  4 5 20
  1 5 100
  Sample Output
  90
  Hint
  INPUT DETAILS:

There are five landmarks.

OUTPUT DETAILS:

Bessie can get home by following trails 4, 3, 2, and 1.

题目链接：https://cn.vjudge.net/contest/242149#problem/A

题目大意：给你一个图，求从N到1的最短路径，并输出路径长度（题目中说一定存在这样的路径，并且1和N也一定是不同的两点，这样就少了许多判断）。第一行给出T,N，T是图中边的条数，N是点的个数，下面T行给出每一条路的具体信息。
我用的存图的方法是邻接表，然后加上Dijkstra算法。Dijkstra算法主要思路就是从开始点开始，设开始点距离为0，其他点的距离为无穷大，然后遍历当前点到下一个点的距离，去松弛其他点到起始点的距离（如果从当前路径到下一个点比其他路径到下一点距离短则更改），然后选取其中离起始点最近的一个点重复刚才的工作，一直到结束点位置以最短路径被选中结束。这里因为涉及到每次都要挑选最短的边，可以使用优先队列来减少代码量和时间复杂度。

#include<cstdio>
#include<iostream>
#include<cstring>
#include<queue>
using namespace std;
const int maxn = 2e5+5;

struct edge
{
    int to, w, ne;
}e[maxn];

struct node
{
    int pos, cost;
    node(){}
    node(int pos,int cost): pos(pos), cost(cost){}
    bool operator < (const node& obj) const
    {
        return cost > obj.cost;
    }
};
int head[maxn], dis[maxn], book[maxn];
int cnt = 0;

void add(int a, int b, int w)
{
    e[cnt].to = b;
    e[cnt].w = w;
    e[cnt].ne = head[a];
    head[a] = cnt++;
}


void init()
{
    cnt = 0;
    memset(dis, 0x3f3f3f3f, sizeof(dis));
    memset(book, 0, sizeof(book));
    memset(head, -1, sizeof(head));
}

void dijtstra(int sx, int ex)
{
    priority_queue<node> q;
    dis[sx] = 0;
    q.push(node(sx, 0));

    while(q.size())
    {
        node temp = q.top();
        q.pop();

        if(book[temp.pos])  continue ;
        book[temp.pos] = 1;
        if(temp.pos == ex)  break ;
        for(int i = head[temp.pos]; i != -1; i = e[i].ne)
            if(dis[e[i].to] > dis[temp.pos] + e[i].w)
            {
                dis[e[i].to] = dis[temp.pos] + e[i].w;
                q.push(node(e[i].to, dis[e[i].to]));
            }
    }
    printf("%d\n", dis[ex]);
}

int main()
{
    int N, T;
    scanf("%d%d", &T, &N);
    init();
    for(int i =  0; i < T; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        add(a, b, w);
        add(b, a, w);
    }

    dijtstra(N, 1);
    return 0;
}