最短路专题+dijkstra 重边

题目链接：https://vjudge.net/contest/281858#problem/A
题目大意：给了一个无向图，输入t和n， t代表几个顶点，n代表问的是从第一个顶点到第n的顶点的最短距离，各种最短路算法的模板题

唯一的坑点：有重边，对dijkstra的邻接表来说，不用考虑。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <functional>
#include <map>
#include <string>
#include <vector>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#define ll long long
using namespace std;
const int maxn=1005;

vector< pair<int ,int > > e[maxn];
int n, m;
int dis[maxn];   //dis当前的最短路
int vis[maxn];

priority_queue<pair<int, int> > q;
int dijkstra(int s, int t)
{
    while(!q.empty())
    {
        q.pop();
    }
    dis[s]=0;
    q.push(make_pair(-dis[s], s));

    while(!q.empty())
    {
        int now=q.top().second;                //一定是最短路上的顶点
        q.pop();
        if(vis[now])
        {
            continue;
        }
        vis[now]=1;
        for(int i=0;i<e[now].size();i++)       //访问所有的邻接点
        {
            int v=e[now][i].first;
            if(!vis[v]&&dis[v]>dis[now]+e[now][i].second)
            {
                dis[v]=dis[now]+e[now][i].second;
                q.push(make_pair(-dis[v], v));//把可能的最短路顶点加入队列
            }
        }
    }
    if(dis[t]==1e9)
    {
        return -1;                            //s-t没有通路
    }
    else
    {
        return dis[t];
    }

}

int main()
{
    scanf("%d%d",&m,&n);
    for(int i=0;i<maxn;i++)   //初始化
    {
        vis[i]=0;
        dis[i]=1e9;
        e[i].clear();
    }

    for(int i=0;i<m;i++)
    {
        int x, y, z;
        scanf("%d%d%d",&x,&y,&z);
        e[x].push_back(make_pair(y ,z));
        e[y].push_back(make_pair(x ,z));
    }
    printf("%d\n",dijkstra(1, n));

    return 0;
}