1504:특정한 최단 경로

조건이 있는 다익스트라

1)조건 없을시 최단경로

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int N, E, V1, V2;
const int MAX = 21e8;
struct Node {
	int to;
	int weight;
};
vector<vector<Node>>alist;
bool operator<(Node v, Node t) {
	if (t.weight < v.weight)return 1;
	if (t.weight > v.weight)return 0;
	if (t.to > v.to)return 1;
	if (t.to < v.to)return 0;
	return 0;
}
priority_queue<Node>q;
vector<int>result;
vector<bool>visited;
int main() {
	freopen_s(new FILE*, "input.txt", "r", stdin);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin >> N >> E;//양방향 간선
	alist.resize(N + 1);
	visited.resize(N + 1);
	result.resize(N + 1);
	std::fill(visited.begin(), visited.end(), false);
	std::fill(result.begin(), result.end(), MAX);
	result[1] = 0;
	visited[1] = false;
	for (int i = 0; i < E; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		alist[a].push_back({ b,c });
		alist[b].push_back({ a,c });
	}
	q.push({ 1,0 });
	while (!q.empty()) {
		Node now = q.top();
		q.pop();
		if (visited[now.to] == 1)continue;
		visited[now.to] == 1;
		for (int i = 0; i < alist[now.to].size(); i++) {
			Node next = alist[now.to][i];
			int total = result[now.to] + next.weight;
			if (total < result[next.to]) {
				result[next.to] = total;
				q.push({ next.to,total });
			}
		}
	}
	cout << result[N];
	return 0;
}

[출력]
4

[조건 있을시]