hdu 2544

代码：

邻接表+优先队列实现

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
struct edge{
    int to,w;
    edge(int a,int b) {to=a;w=b;}
};
vector<edge>e[105];
struct node{
    int id,dis;
    node(int a,int b){id=a;dis=b;}
    bool operator<(const node&a ) const
    {return dis>a.dis;}
};
int n,m;
int pre[105];    //记录前驱结点 
void print(int s,int t) {
    if(s==t) {printf("%d ",s); return;}//打印起点 
    print(s,pre[t]);//先打印前一个点 
    printf("%d ",t);//后打印当前点，最后打印的是终点t 
}//打印从s到t的最短路径 
void dijkstra() {
    int s=1;    //起点是1 
    int dis[105];//记录所有结点到起点的距离 
    bool done[105];//done[i]=true表示到结点i的最短路径已经找到 
    for(int i=1;i<=n;++i) {
        dis[i]=inf;    done[i]=false;
    }
    dis[s]=0;    //起点到自己的距离是0
    priority_queue<node>q;//优先队列，存结点的信息
    q.push(node(s,dis[s]));//起点进栈
    while(!q.empty()) {
        node u=q.top();
        q.pop();
        if(done[u.id]) continue;//丢弃已经找到最短路径的结点，即集合A中的结点
        done[u.id]=true;
        for(int i=0;i<e[u.id].size();++i) {
            edge y=e[u.id][i];    //u.id的第i个邻居是y.to 
            if(done[y.to])    continue;//丢弃已经找到最短路径的邻居结点 
            if(dis[y.to]>y.w+u.dis) {
                dis[y.to]=y.w+u.dis;
                q.push(node(y.to,dis[y.to]));//扩展新的邻居，放到优先队列中 
                pre[y.to]=u.id;//如有需要，打印路径 
            }
        }//检查结点u的所有邻居 
    }
    printf("%d\n",dis[n]);
    //print_path(s,n);
}
int main() {
    while(~scanf("%d%d",&n,&m)) {
        if(!n&&!m)    return 0;
        for(int i=1;i<=n;++i) e[i].clear();
        while(m--) {
            int a,b,c;
            scanf("%d%d%d",&a,&b,&c);
            e[a].push_back(edge(b,c));
            e[b].push_back(edge(a,c));
        }
        dijkstra();
    }
}