首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >Code Forces 26C Dijkstra?

Code Forces 26C Dijkstra?

作者头像
ShenduCC
发布2018-04-26 16:14:13
8190
发布2018-04-26 16:14:13
举报
文章被收录于专栏:算法修养算法修养

C. Dijkstra?

time limit per test

1 second

memory limit per test

64 megabytes

input

standard input

output

standard output

You are given a weighted undirected graph. The vertices are enumerated from 1 to n. Your task is to find the shortest path between the vertex 1 and the vertex n.

Input

The first line contains two integers n and m (2 ≤ n ≤ 105, 0 ≤ m ≤ 105), where n is the number of vertices and m is the number of edges. Following m lines contain one edge each in form aibi and wi (1 ≤ ai, bi ≤ n, 1 ≤ wi ≤ 106), where ai, bi are edge endpoints and wi is the length of the edge.

It is possible that the graph has loops and multiple edges between pair of vertices.

Output

Write the only integer -1 in case of no path. Write the shortest path in opposite case. If there are many solutions, print any of them.

Examples

input

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

output

1 4 3 5 

input

5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1

output

1 4 3 5 

在Dijstra上优化一下,就是用优先队列去找最小的值

#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <queue>
#include <stdio.h>
#include <vector>

using namespace std;
const long long int INF=(long long int )1<<60;
#define MAX 100000
vector< pair<int,int> > a[MAX+5];
struct Node
{
    int pos;
    int value;
    Node(){};
    Node(int pos,int value)
    {
        this->pos=pos;
        this->value=value;
    }
    friend bool operator <(Node a,Node b)
    {
        return a.value>b.value;
    }
};
priority_queue<Node>q;
int vis[MAX+5];
long long int d[MAX+5];
int pre[MAX+5];
int n,m;
void Dijstra()
{
    memset(vis,0,sizeof(vis));
    for(int i=1;i<=n;i++)
        d[i]=INF;
    pre[1]=-1;
    d[1]=0;
    q.push(Node(1,0));
    while(!q.empty())
    {
        Node term=q.top();
        q.pop();
        if(vis[term.pos]) continue;
        vis[term.pos]=1;

        for(int i=0;i<a[term.pos].size();i++)
        {
            int v=a[term.pos][i].first;
            int w=a[term.pos][i].second;
            if(!vis[v]&&d[term.pos]+w<d[v])
            {
               d[v]=d[term.pos]+w;
               pre[v]=term.pos;
               q.push(Node(v,d[v]));
            }
        }
    }
}
void print(int x)
{
    if(x==-1)
        return;
    print(pre[x]);
    if(x==n)
        cout<<x<<endl;
    else
        cout<<x<<" ";
}
int main()
{

    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        a[i].clear();
    int x,y,z;

    for(int i=1;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        a[x].push_back(make_pair(y,z));
        a[y].push_back(make_pair(x,z));
    }
    Dijstra();
    if(d[n]==INF)
        printf("-1\n");
    else
        print(n);
    return 0;
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2016-04-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档