앳코더90 - 013 - Passing（★5）

https://atcoder.jp/contests/typical90/tasks/typical90_m

013 - Passing（★5）

 

정점 N, 간선 M이 1 2 3 으로 M개 주어진다. k = 1~N까지 1 -> k -> N의 최단 경로를 출력하라 라는 문제다. 크게 어렵지 않게 접근할 수 있었는데, 먼저 플로이드워셜 생각을 했다가 메모리가 부족하여 dijk(1) + dijk(N)을 더하는 형태로 구현했다. int로 했다가 오버플로우로 틀려서 ll로 수정하니 정답이 나왔다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_set>
#include <numeric>
#include <random>
#include <iostream>

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define rep1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define range(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define pb push_back
#define x first
#define y second

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
typedef vector<int> vi;
typedef vector<long long> vll;

const ll INF = 20000000000000000;
const double pi = 3.14159265358979;
const ll MOD = 987654321;

void yesno(bool a)
{
	if (a)
		cout << "Yes\n";
	else
		cout << "No\n";
}

vector<pll> graph[100002];
ll dist[100002];
ll ans[100002];
ll a, b, c;
int N, M;

void dijk(int C)
{
	for (int i = 1; i <= N; i++)
		dist[i] = INF;

	priority_queue<pair<ll, ll>> pq;
	pq.push({ 0, C });
	dist[C] = 0;

	while (!pq.empty())
	{
		ll cost = -pq.top().first;
		ll cur = pq.top().second;
		pq.pop();

		for (int j = 0; j < graph[cur].size(); j++)
		{
			ll next = graph[cur][j].first;
			ll nCost = graph[cur][j].second;

			if (dist[next] > cost + nCost)
			{
				dist[next] = cost + nCost;
				pq.push(make_pair(-dist[next], next));
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	cin >> N >> M;

	rep(i, M)
	{
		int a, b, c;
		cin >> a >> b >> c;
		graph[a].push_back({ b,c });
		graph[b].push_back({ a,c });
	}

	dijk(1);
	for (int i = 1; i <= N; i++)
		ans[i] += dist[i];
	dijk(N);
	for (int i = 1; i <= N; i++)
		ans[i] += dist[i];

	for (int i = 1; i <= N; i++)
		cout << ans[i] << '\n';
	

	return 0;
}

 

https://b1ackhand.tistory.com/249

다익스트라

 

다익 템플릿