input

第一行表示这个图有4条边，下面五行代表这个图的5条边。

4
0 2 2
0 1 5
1 3 2
2 3 6
-1 0 0

输入样例

out

分别输出结点“0”到结点0,1,2,3的最短距离。

0 5 2 7

源码

#include <queue>
#include <vector>
#include <cstdio>
using namespace std;
#define MAX 10000
#define INF 10000

class edge{
public:

    int to,cost;
    edge(int to,int cost)
    {
        this->to=to;
        this->cost=cost;
    }

};

vector<edge> G[MAX];
int d[MAX];
int v;

typedef pair<int,int> P;

void build()
{
    printf("input v\n");
    scanf("%d",&v);
    while(true)
    {
        int from,to,cost;
        scanf("%d %d %d",&from,&to,&cost);
        if(from<0)
        {
            break;
        }
        G[from].push_back(edge(to,cost));
        G[to].push_back(edge(from,cost));

    }
}

void dijkstra(int s)
{
    priority_queue< P,vector<P>,greater<P> > que;
    fill(d,d+v,INF);
    d[s]=0;
    que.push(P(0,s));

    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int v = p.second;
        if(d[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++)
        {
            edge e = G[v][i];
            if(d[e.to]>d[v]+e.cost)
            {
                d[e.to]=d[v]+e.cost;
                que.push(P(d[e.to],e.to));
            }
        }
    }
}

vector<int> get_path(int des)
{
    vector<int> res;
    res.push_back(des);
    //printf("lalalala\n");
    while(des!=0)
    {

        vector<edge> edges = G[des];
        //printf("size of edges: %d\n",edges.size());
        for(int i=0;i<edges.size();i++)
        {
            //printf("%d %d\n",edges[i].to,edges[i].cost);
            if(d[des]==d[edges[i].to]+edges[i].cost)
            {
                //printf("前驱结点是：%d",i);
                res.push_back(edges[i].to);
                des = edges[i].to;
                break;
            }
        }
    }
    return res;
}

int main()
{
    build();
    dijkstra(0);
    for(int i=0;i<v;i++)
    {
        printf("%d ",d[i]);
    }
    vector<int> res = get_path(3);
    printf("从终点3到起点1的最短路径是：\n");
    for(int i=0;i<res.size();i++)
    {
        printf("%d ",res[i]);
    }

}