[백준] 9323: 무임승차

0. 문제 주소

 

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

9323번: 무임승차

 

 

1. 풀이

 

 

아래 문장이 굉장히 중요하다.

 

기차 티켓은 기본 s원에 출발지 A와 도착지 B 사이의 최단거리에 비례하여 1 킬로미터당 p의 요금이 추가된다. 당연히 이 티켓으로는 A와 B 사이를 최단거리로 운행하는 기차만 탈 수 있다.

 

당연히 인접한 역 사이에서만 티켓을 끊을 수 있을 줄 알았는데, 떨어져 있어도 가능했다.

 

다시 말해서 edge를 거칠 때마다 기본 요금을 낼 필요가 없다는 것이다.

 

위의 예시에선 1에서 3으로 가는 티켓을 끊으면, 기본 요금 s는 한 번만 내고, 최단거리인 100에 p를 곱한 값만 더 내주면 된다.

 

 

맨 처음엔 edge별로 티켓을 끊을지, 무임승차를 할지에 대해서 비교를 해주고 더 싼 값을 weight로 저장해서 풀었는데 틀렸다. 하긴 그러면 플레5가 아니겠지..

 

여기저기 참고를 해본 결과 dp 테이블로 dp[node][i] = start에서 node까지 가는 최소 비용(i가 0이면 값 지불, 1이면 무임승차)

 

그래서 다익스트라 알고리즘을 돌리며 아래와 같이 dp 테이블을 갱신해 주어야 한다.

 

dp[next][0] = min(dp[next][0], min(dp[curr][0] + next_weight*p*1., dp[curr][1] + next_weight*p*1. + s));
dp[next][1] = min(dp[next][1], min(dp[curr][0], dp[curr][1]) + (y + next_weight*p)*(next_prob/100.0));

 

 

 

2. 풀이 코드

 

* 유의할 점

#######

 

#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <algorithm>
#include <string>

#define pii pair<int, int>
#define piii pair<int, pii>
#define pid pair<int, double>
#define pdi pair<double, int>
#define MAX 205
#define INF 987654321.0

using namespace std;

int T;
int N, M, S, E, s, p, y;
int u, v, prob, w;
vector<piii> graph[MAX];
double dist[MAX];
double dp[MAX][2]; // 0: paid, 1: free
bool visited[MAX];




int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d", &T);
    while(T>0){
       T--;
       
       scanf("%d %d %d %d %d %d %d", &N, &M, &S, &E, &s, &p, &y);
       
       for (int i=1;i<=N;i++){
           graph[i].clear();
       }
       
       fill(dist+1, dist+N+1, INF);
       memset(visited, 0, sizeof(visited));
       for (int i=1;i<=N;i++){
           dp[i][0] = dp[i][1] = INF;
       }
       
       for (int i=0;i<M;i++){
           scanf("%d %d %d %d", &u, &v, &prob, &w);
           graph[u].push_back(piii(v, pii(prob, w)));
           graph[v].push_back(piii(u, pii(prob, w)));
       }
       
       dp[S][0] = s*1.;
       dp[S][1] = 0.;
       dist[S] = 0.;
       priority_queue<pdi, vector<pdi>, greater<pdi>> PQ;
       PQ.push(pdi(dist[S], S));
       while(!PQ.empty()){
           auto ppp = PQ.top();
           PQ.pop();
           int curr = ppp.second;
           double curr_dist = ppp.first;
           if (visited[curr]) continue;
           visited[curr] = true;
           for (auto pp: graph[curr]){
               int next = pp.first;
               int next_prob = pp.second.first, next_weight = pp.second.second;
               dp[next][0] = min(dp[next][0], min(dp[curr][0] + next_weight*p*1., dp[curr][1] + next_weight*p*1. + s));
               dp[next][1] = min(dp[next][1], min(dp[curr][0], dp[curr][1]) + (y + next_weight*p)*(next_prob/100.0));
               double final_weight = min(dp[next][0], dp[next][1]);
               if (dist[next] > final_weight){
                   dist[next] = final_weight;
                   PQ.push(pdi(dist[next], next));
               }
           }
       }
       
       printf("%.2f\n", dist[E]);
       
       
   }

    return 0;
}