出门旅行(tour)

题目描述:

在神奇的 oi 国度，有 n 个城市 m 条双向道路，每条道路连接了两个不同的城市。寒假到了，小 S 决定出门旅游一趟。因为以往跟团旅游多了，这次小 S 决定自驾游。对于自驾游，小 S 最关心的自然是燃油的耗费，为了省钱，小 S 请你帮他找一条最短的路。

输入格式:

第一行两个整数 n,m，表示有 n 个城市和 m 条双向道路。城市从 1..n 编号。
接下来 m 行，每行三个正整数 a,b,c，表示 a 和 b 之间有一条长为 c 的双向道路。a,b 不相同，且 c 不超过 1000
注意：两个城市之间可能会有多条双向道路。
接下来一行两个整数，s,t，表示小 S 本次旅行的出发地和目的地。s,t 不相同。

输出格式:

仅一行一个整数，表示最短的距离。如果不能到达，请输出-1。

样例输入:

3 3

1 2 1

1 3 3

2 3 1

1 3

样例输出:

2

提示:

【样例解释】
1->2->3 即是最优解。
【数据范围】
对于 30%的数据，n<=100,m<=1000
对于 100%的数据，n<=2000,m<=100000

时间限制:1000ms
空间限制:128MByte

#include<bits/stdc++.h>

using namespace std;

int n, m;

struct enode{

    int y, z;

    enode(int y1, int z1) : y(y1), z(z1) {}

};

struct node{

    int dis, v;

    node(int x1, int y1) : dis(x1), v(y1) {}

    bool operator < (const node &a) const

    {

        return dis > a.dis;

    }

};

vector<enode> e[];

priority_queue<node> q;

int dis[];

bool vis[];

int main()

{

    int x, y, z, s, t, v;

    cin>>n>>m;

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

        cin>>x>>y>>z;

        e[x].push_back(enode(y, z));

        e[y].push_back(enode(x, z));

    }

    memset(dis, 0x3f3f3f3f, sizeof(dis));

    memset(vis, , sizeof(vis));

    cin>>s>>t;

    dis[s] = ;

    q.push(node(, s));

    while(!q.empty()){

        v = q.top().v;

        q.pop();

        if(vis[v]) continue;

        vis[v] = ;

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

            if(dis[v] + e[v][i].z < dis[e[v][i].y]){

                dis[e[v][i].y] = dis[v] + e[v][i].z;

                q.push(node(dis[e[v][i].y], e[v][i].y));

            }

    }

    if(dis[t] == 0x3f3f3f3f) cout<<-<<endl;

    else cout<<dis[t]<<endl;

    return ;

}