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 ai, bi 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 1output
1 4 3 5 input
5 6
1 2 2
2 5 5
2 3 4
1 4 1
4 3 3
3 5 1output
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;
}腾讯云开发者
