最短路（模版）题解

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll g_llN = 0;
ll g_llM = 0;
ll g_llS = 0;
ll g_llDis[200005] = {0};
vector<pair<ll, ll>> g_vecA[10005];
queue<ll> g_qQ;
bool g_bVal[200005] = {false};

void bfs()
{
	for (ll i = 1; i <= g_llN; i++)
	{
		g_llDis[i] = 1e9;
	}
	
	g_llDis[g_llS] = 0;
	g_qQ.push(g_llS);
	g_bVal[g_llS] = true;
	
	while (!g_qQ.empty())
	{
		ll llT = g_qQ.front();
		g_qQ.pop();
		
		g_bVal[llT]= false;
		
		for (ll i = 0; i < g_vecA[llT].size(); i++)
		{
			if (g_llDis[g_vecA[llT][i].first] > 
			(g_llDis[llT] + g_vecA[llT][i].second))
			{
				g_llDis[g_vecA[llT][i].first] = g_llDis[llT] + 
				g_vecA[llT][i].second;
				
				if (g_bVal[g_vecA[llT][i].first])
				{
					continue;
				}
				
				g_bVal[g_vecA[llT][i].first] = true;
				g_qQ.push(g_vecA[llT][i].first);
			}
		}
	}
}

int main()
{
	cin >> g_llN >> g_llM >> g_llS;
	
	for (ll i = 1; i <= g_llM; i++)
	{
		ll llU = 0;
		ll llV = 0;
		ll llW = 0;
		
		cin >> llU >> llV >> llW;
		
		g_vecA[llU].push_back({llV, llW});
	}
	
	bfs();
	
	for (ll i = 1; i <= g_llN; i++)
	{
		if (1e9 == g_llDis[i])
		{
			cout << (ll)((1 << 31) - 1) << " ";
		}
		else
		{
			cout << g_llDis[i] << " ";
		}
	}
	
	cout << endl;
	
	return 0;
}