주말 여행 계획 - 15808

//15808 - 주말 여행 계획
 
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
#define INF 1000000000
 
int N;
vector<vector<pair<int, int>>> adj;
 
void init()
{
    cin >> N;
    adj = vector<vector<pair<int, int>>>(N+2);
    int c;
    for(int i = 1; i<=N; ++i)
        for(int j = 1; j<=N; ++j)
        {
            cin >> c;
            if(c)
                adj[i].push_back(make_pair(j, c)), adj[j].push_back(make_pair(i, c));
        }
    int q, w;
    cin >> q >> w;
    int x, y;
    for(int i = 0; i<q; ++i)
    {
        cin >> x >> y;
        adj[0].push_back(make_pair(x, -y));
    }
    for(int i = 0; i<w; ++i)
    {
        cin >> x >> y;
        adj[x].push_back(make_pair(N+1, -y));
    }
}
 
void dijkstra()
{
    priority_queue<pair<int, int>> pq;
    vector<int> dist(N+2, INF);
    pq.push(make_pair(0, 0));
    dist[0] = 0;
 
    while(!pq.empty())
    {
        int here = pq.top().second;
        int cost = -pq.top().first;
        pq.pop();
 
        if(dist[here] < cost) continue;
 
        for(int i = 0; i<adj[here].size(); ++i)
        {
            int there = adj[here][i].first;
            int c = adj[here][i].second;
 
            if(c+cost < dist[there])
            {
                dist[there] = c+cost;
                pq.push(make_pair(-c-cost, there));
            }
        }
    }
    cout << -dist[N+1];
}
 
int main()
{
    ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    init();
    dijkstra();
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/15808

15808번: 주말 여행 계획

 

 

 

 

 

 

주말 여행 계획

여행지와 숙소 한곳씩만 들려 기대값이 최대가 되게 만들어 주면 됩니다.

이때 노드 두개를 추가하면 다익스트라 한번에 답을 구할수 있는데,

시작노드와 여행지들을 여행지의 기대값의 음수값을 가중치로 하는 단방향 간선으로 연결하고

도착노드와 숙소들을 숙소의 기대값의 음수값을 가중치로 하는 단방향 간선으로 연결한다음,

시작노드에서 도착노드까지의 최단거리를 구하면 됩니다.

음수간선이 있지만 단방향 간선에 시작노드는 들어오는 간선이 없고 도착노드는 나가는 간선이 없어 싸이클이 발생하지 않고, 또한 경로에서 발생하는 피로도는 모두 음이아닌 정수이기 때문에 오직 하나의 여행지와 숙소를 거치는것이 최단거리가 될것입니다.