lev36 2번

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

int N, M, K, A, B;
struct Node {
	int n;
	int price;
};
bool operator<(Node v, Node t){
	return t.price < v.price;
}
queue<Node>q;
int result[1001];
const int MAX = 21e8;
int main() {
	cin >> N >> M >> K;
	cin >> A >> B;
	A = A - 1;
	B = B - 1;
	vector<vector<Node>>alist(N + 1);
	for (int i = 0; i <M; i++) {
		int from;
		int to;
		int price;
		cin >> from >> to >> price;
		alist[from-1].push_back({ to-1,price });
	}
	for (int i = 0; i < N; i++) {
		result[i] = MAX;
	}
	result[0] = 0;
	q.push({ 0,0 });
	while (!q.empty()) {
		Node now = q.front();
		q.pop();
		if (result[now.n] < now.price)continue;
		for (int i = 0; i < alist[now.n].size(); i++) {
			Node next = alist[now.n][i];
			int total = now.price + next.price;
			if (result[next.n] >total) {
				result[next.n] = total;
				q.push({ next.n, total });
			}
		}
	}
	cout << result[B] << "\n";
	int p;
	
	return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K;
int A, B;
const int MAX= 21e5;
int result[1001];
int year[30001];
struct Node {
	int n;
	int price;
};
vector<vector<Node>>alist(1001);
bool operator<(Node v, Node t) {
	return t.price<v.price;
}
priority_queue<Node>q;
void input() {
	cin >> N >> M >> K;
	cin >> A >> B;
	A = A - 1;
	B = B - 1;
	for (int i = 0; i < M; i++) {
		int f, t, c;
		cin >> f >> t >> c;
		alist[f - 1].push_back({ t - 1,c });
	}
	for (int i = 0; i < N; i++) {
		result[i] = MAX;
	}
	q.push({ 0,0 });
}
void go() {
	while (!q.empty()) {
		Node now = q.top();
		q.pop();
		if (result[now.n] < now.price)continue;

		for (int i = 0; i < alist[now.n].size(); i++) {
			Node next = alist[now.n][i];
			//next.price에 p만큼 더해주면 안되나?
			int total = (next.price) + now.price;
			if (result[next.n] > total) {
				result[next.n] = total;
				q.push({ next.n,total });
			}
		}
	}
	cout << result[B];
}
int main() {
	
	input();
	
	return 0;
}

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, M, K;
int A, B;
const int MAX = 21e8;
int result[1001];
int year[30001];
struct Node {
    int n;
    int price;
};
vector<vector<Node>> alist(1001);
bool operator<(Node v, Node t) {
    return t.price < v.price;
}
priority_queue<Node> q;
void input() {
    cin >> N >> M >> K;
    cin >> A >> B;
    A = A - 1;
    B = B - 1;
    for (int i = 0; i < M; i++) {
        int f, t, c;
        cin >> f >> t >> c;
        alist[f - 1].push_back({ t - 1,c });
    }
    for (int i = 0; i < N; i++) {
        result[i] = MAX;
    }
    q.push({ 0,0 });
    for (int i = 0; i < K; i++) {
        int a;
        cin >> a;
    }
}
void go() {

    while (!q.empty()) {
        Node now = q.top();
        q.pop();
        if (result[now.n] < now.price) continue;

        for (int i = 0; i < alist[now.n].size(); i++) {
            Node next = alist[now.n][i];
            int total = (next.price) + now.price;
            if (result[next.n] > total) {
                result[next.n] = total;
                q.push({ next.n,total });
            }
        }
    }
    cout << result[B] << "\n";
}
int main() {

    input();
    go();
    for (int i = 0; i < N; i++) {
        result[i] = MAX;
    }
    result[0] = 0;
    q.push({ 0,0 });

    // 두 번째 최솟값을 출력하기 전에 next.price에 3 더하기
    while (!q.empty()) {
        Node now = q.top();
        q.pop();
        if (result[now.n] < now.price) continue;

        for (int i = 0; i < alist[now.n].size(); i++) {
            Node next = alist[now.n][i];
            int total = (next.price + 3) + now.price; // 여기에서 3을 더합니다.
            if (result[next.n] > total) {
                result[next.n] = total;
                q.push({ next.n,total });
            }
        }
    }
    cout << result[B] << "\n";

    return 0;
}

#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int N, M, K;
int A, B;
const int MAX = 21e8;
int result[1001];
int year[30001];
struct Node {
    int n;
    int price;
};
vector<vector<Node>> alist(1001);
bool operator<(Node v, Node t) {
    return t.price < v.price;
}
priority_queue<Node> q;
void input() {
    cin >> N >> M >> K;
    cin >> A >> B;
    A = A - 1;
    B = B - 1;
    for (int i = 0; i < M; i++) {
        int f, t, c;
        cin >> f >> t >> c;
        alist[f - 1].push_back({ t - 1,c });
    }
   
    for (int i = 0; i < K; i++) {
        cin >> year[i];
    }
  
}
void go(int x) {
    for (int i = 0; i < N; i++) {
        result[i] = MAX;
    }
    result[0] = 0;
    q.push({ 0,0 });
    while (!q.empty()) {
        Node now = q.top();
        q.pop();
        if (result[now.n] < now.price) continue;

        for (int i = 0; i < alist[now.n].size(); i++) {
            Node next = alist[now.n][i];
            int total = (next.price+x) + now.price;
            if (result[next.n] > total) {
                result[next.n] = total;
                q.push({ next.n,total });
            }
        }
    }
    cout << result[B] << "\n";
}
int main() {

    input();
    go(0);
    for (int i = 0; i < K; i++) {
        go(year[i] + i);
    }
 
   

    return 0;
}