Light OJ 1019 - Brush (V)（图论-dijkstra）

题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1019

题目大意：Tanvir想从节点1的位置走到节点n的位置， 输出最短距离， 如果不存在输出"Impossible".

解题思路：dijkstra模版题

代码如下：

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int INF = 0x3f3f3f3f;

const int N = ;

int dis[N];

vector<pair<int, int> > vec[N];

priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > >que;

void dijkstra()

{

    dis[] = ;

    que.push(make_pair(, ));

    while(!que.empty())

    {

        pair<int, int> p = que.top();

        que.pop();

        int v = p.second;

        if(dis[v] < p.first)

            continue;

        for(int i=; i<vec[v].size(); ++ i)

        {

            pair<int, int> t = vec[v][i];

            if(dis[t.second] > dis[v] + t.first)

            {

                dis[t.second] = dis[v] + t.first;

                que.push(make_pair(dis[t.second], t.second));

            }

        }

    }

}

void solve(int cases)

{

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

    {

        dis[i] = INF;

        vec[i].clear();

    }

    while(!que.empty())

        que.pop();

    int n, m;

    scanf("%d%d", &n, &m);

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

    {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        vec[u].push_back(make_pair(w, v));

        vec[v].push_back(make_pair(w, u));

    }

    dijkstra();

    if(dis[n] == 0x3f3f3f3f)

        printf("Case %d: Impossible\n", cases);

    else

        printf("Case %d: %d\n", cases, dis[n]);

}

int main()

{

    int T;

    scanf("%d", &T);

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

        solve(i);

    return ;

}

Light OJ 1019 - Brush (V)（图论-dijkstra）的相关教程结束。