Code Forces 26C Dijkstra?

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏python3

python for循环

当range执行完之后,代码执行else部分代码。如果遇到break,终止循环,不会走else代码

37710
来自专栏java学习

Java每日一练(2017/8/21)

每日一句 学的到东西的事情是锻炼,学不到的是磨练。 查看以前的所有练习题目以及答案:https://mp.weixin.qq.com/mp/homepage?_...

365160
来自专栏AI研习社

最常见的 35 个 Python 面试题及答案(2018 版)

作为一个 Python 新手,你必须熟悉基础知识。在本文中我们将讨论一些 Python 面试的基础问题和高级问题以及答案,以帮助你完成面试。包括 Python ...

92130
来自专栏nummy

python operator模块学习

operator模块是python中内置的操作符函数接口,它定义了一些算术和比较内置操作的函数。operator模块是用c实现的,所以执行速度比python代码...

9020
来自专栏java学习

第2天的练习

大家把答案在留言区留下来 1:什么是变量?变量的定义格式?要使用变量需要注意什么? 2:Java中的数据类型分几类?基本数据类型有哪些? 3:数据类型转换: ...

37770
来自专栏逆向技术

C语言第四讲,typedef 关键字,以及作用域

        C语言第四讲,typedef 关键字,以及作用域 一丶typedef关键字   在C语言中,有typedef 关键字,这个关键字的作用就是允许你...

29550
来自专栏Linux驱动

29.C++- 异常处理

C++内置了异常处理的语法元素 try catch try语句处理正常代码逻辑 当try语句发现异常时,则通过throw语句抛出异常,并退出try语句 catc...

30360
来自专栏抠抠空间

细数Python中的数据类型以及他们的方法

一、数据类型的种类及主要功能 1、数字类型   数字类型主要是用来计算,它分为整数类型int和浮点类型float 2、布尔类型   布尔类型主要是用于判断,它分...

34250
来自专栏pangguoming

理解js中的new

new 操作符 在有上面的基础概念的介绍之后,在加上new操作符,我们就能完成传统面向对象的class + new的方式创建对象,在Javascript中,我们...

42940
来自专栏JavaEdge

青铜到王者 ,快速提升你 Go语言的段位! "狗"语言实战(二)- 基础语法1 变量定义

15140

扫码关注云+社区

领取腾讯云代金券