Решение задачи Алгоритм Дейкстры? с Codeforces

Без пояснения   Просмотров: 49


Задан неориентированный взвешенный граф, вершины которого пронумерованы от 1 до n. Ваша задача найти кратчайший путь из вершины 1 в вершину n.

Код

#include<bits/stdc++.h>
#define ll long long int
ll parent[100010]={};
using namespace std;


void print(ll n)
{
	if(n==1)
	{
		cout<<1<<" ";
		return;
	}
	
	print(parent[n]);
	cout<<n<<" ";
}

int main()
{
	ll n,m;
	cin>>n>>m;
	vector<ll> edg[100005];
	map<pair<ll,ll>,ll> cost;
	for(ll i=0;i<m;i++)
	{
		ll u,v,w;
		cin>>u>>v>>w;
		edg[v].push_back(u);
		edg[u].push_back(v);
		cost[{u,v}]=w;
		cost[{v,u}]=w;
		
	}	
	
	ll dist[n+10];
	for(ll i=1;i<=n;i++)dist[i]=100000000000;
	dist[1]=0;
	priority_queue<ll> pq;
	
	pq.push(1);
	
	
	
	
	
	while(!pq.empty())
	{
		ll u=pq.top();
		pq.pop();
		
		for(ll i=0;i<edg[u].size();i++)
		{
			ll v=edg[u][i];
			if(dist[u]+cost[{u,v}]<dist[v])
			{
				dist[v]=dist[u]+cost[{u,v}];
				parent[v]=u;
				pq.push(v);
				
			}
		}
		
	}
	
	if(dist[n]==100000000000)
	{
		cout<<-1<<endl;
		return 0;
	}
	print(n);
	
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться