（模板）poj2387（dijkstra+优先队列优化模板题）

题目链接：https://vjudge.net/problem/POJ-2387

题意：给n个点(<=1000)，m条边(<=2000)，求结点n到结点1的最短路。

思路：dijkstra优先队列，复杂度O(nlogn)。

AC代码：

#include<cstdio>

#include<queue>

#include<algorithm>

using namespace std;

const int maxn=1e3+;

const int inf=0x3f3f3f3f;

int m,n,cnt,head[maxn],dis[maxn],vis[maxn];

typedef pair<int,int> PII;

priority_queue<PII,vector<PII>,greater<PII> > pq;

struct node{

    int v,w,nex;

}edge[maxn<<];

void adde(int u,int v,int w){

    edge[++cnt].v=v;

    edge[cnt].w=w;

    edge[cnt].nex=head[u];

    head[u]=cnt;

}

void dijkstra(){

    pq.push(make_pair(,n));

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

        dis[i]=inf;

    dis[n]=;

    int num=;

    while(!pq.empty()&&num<=n){

        int d=pq.top().first,u=pq.top().second;

        pq.pop();

        if(vis[u]) continue;

        vis[u]=;

        ++num;

        for(int i=head[u];i;i=edge[i].nex){

            int v=edge[i].v,w=edge[i].w;

            if(!vis[v]&&dis[v]>dis[u]+w){

                dis[v]=dis[u]+w;

                pq.push(make_pair(dis[v],v));

            }

        }

    }

}

int main(){

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

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

        int u,v,w;

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

        adde(u,v,w);

        adde(v,u,w);

    }

    dijkstra();

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

    return ;

}