[백준] 16227 의약품 수송

 

문제를 읽으면 그냥 다익스트라처럼 생겼다

그래프를 그리고 내가 최소시간을 들여 원하는 정점으로 가면 된다

 

근데 조건이 하나 붙는다

100을 초과는 거리를 간다면 그때는 연료를 충전해야 한다

이걸 매번 정점에서 하는줄알고 처음에 틀렸다 ㅎㅎ

 

결국 내가 갈수있는 거리도 하나의 가져가야할 데이터가 되므로

테이블을 d[정점의 수][갈 수 있는 거리]로 잡아보자

=> d[1010][111]; 최대 정점은 1000개고 갈수있는 거리는 한번에 100이다

 

그리고 다익스트라를 돌리면서 pq에서 내가 남은거리도 들고다니면 된다

만약 남은거리보다 다음정점까지 거리가 같거나 짧으면 그냥 가면된다

하지만 남은거리가 더 짧으면 시간 5를 추가해 충전하고 주행가능거리를 100이라고 생각하자!

 

그리고 마지막으로 정점 n+1에서 남은시간을 돌아보며 가장 짧은 시간을 찾자

 

소스코드

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
 
int n,k;
int d[1010][111];
 
int main(){
    memset(d,-1,sizeof(d));
 
    scanf(" %d %d",&n,&k);
    vector<vector<pair<int,int>>> Graph(n+3);
 
    for(int i=0;i<k;i++){
        int u,v,c; scanf(" %d %d %d",&u,&v,&c);
        Graph[u].push_back({v,c});
        Graph[v].push_back({u,c});
    }
 
    priority_queue<pair<pair<int,int>,int>> pq;
    pq.push({{0,100},0});
 
    while(!pq.empty()){
        int now = pq.top().second;
        int left = pq.top().first.second;
        int cost = -pq.top().first.first;
        pq.pop();
 
        if(d[now][left] !=-1) continue;
        d[now][left]=cost;
 
        for(int i=0;i<Graph[now].size();i++){
            int next = Graph[now][i].first;
            int ncost = Graph[now][i].second;
            
            int nexttime = -cost-ncost;
            
            if(left>=ncost){
                int diff = left-ncost;
                if(d[next][diff]==-1) pq.push({{nexttime,diff},next});
            } else {
                int diff = 100-ncost;
                if(d[next][diff]==-1) pq.push({{nexttime-5,diff},next});
            }
        }
    }
    
    int ans=1e9;
    for(int i=0;i<=100;i++) {
        if(d[n+1][i]<=0) continue;
        ans = min(ans,d[n+1][i]);
    }
    printf("%d\n",ans);
}