10217

최단거리 + 제한비용 문제이다. 

다익스트라로 해결하면 쉽겠지 하고 생각하다가 곰곰히 생각해보니 순수한 다익스트라 방법으로는 위 문제를 풀 때 예외가 발생한다는 것을 깨달았다.

다익스트라는 

"어느 정점의 최단 경로를 확인 했다면 그 경로와 그와 인접한 정점들의 최단 경로를 연결 할 수 있다" 는 원리로 구할 수 있다

하지만 위 문제에서는

어느 정점의 최단 경로를 확인해도 그 정점과 연결된 다른 정점들과의 최단 경로를 연결 할 수 있다고 말을 할 수가 없다. 왜냐하면 제한비용이 있기 때문이다.

예를 들어

현재 A점에 오는데 두 가지 방법이 있다고 하자 

경로를 (최단거리, 현재 남은 비용)이라 하겠다

(10, 5), (30, 100)

여기서 B점까지 가야한다. 그런데 B점까지 가는 방법으로는 두가지 방법이 있다

(5, 60), (100, 5)

A점까지 최단 거리로 이동하는 경우는 (10, 5)이다. 최단 거리 경로에서는 반드시 (100, 5)인 경로를 선택 할 수 밖에 없다. 그러면 B까지 이동하는데 경로는 110이 된다.

하지만 A점까지 최단 거리가 아니였던 경로 (30, 100)을 이용하면 B점을 이동 할 때 (5, 60)인 경로를 선택 할 수 있다. 따라서 B점까지 이동하는데 경로는 35가 된다.

그러므로 정점으로 이동하는 최단 경로만 보는 것이 아니라 여러가지 경로를 모두 봐야 한다.

하지만 모든 경로들을 다 보면 메모리가 매우 많이 들기 때문에 어떻게 처리할 것인가를 고심하다 정점이 최대 100개이고 비용이 최대 10000인 점을 이용해 배열 내부에 선언이 가능한하다고 판단했고 각 정점들마다 이동하는데 드는 비용에 대한 최단 거리를 저장하는 배열을 선언해서 해결했다.

쉽지 않았지만 풀고나니 개운한 문제였다

#include<cstdio> #include<iostream> #include<vector> #include<queue> #include<fstream> using namespace std; vector<pair<int, int> > outflow_cost[105]; vector<pair<int, int> > outflow_time[105]; int d[105][10005]; class Prove{ public : int pos, cost, time; Prove(int nposition, int ncost, int ntime){ pos = nposition; cost = ncost; time = ntime; } }; class mycomparison { public: bool operator() (const Prove& a, const Prove& b) const { return a.time > b.time; } }; int main(){ int tc; ifstream ifp("input.txt"); ifp>>tc; //scanf("%d", &tc); int N, M, K; for(int clk=0; clk<tc; clk++){ ifp>>N>>M>>K; //scanf("%d %d %d", &N, &M, &K); for(int piv=1; piv<=N; piv++){ outflow_cost[piv].clear(); outflow_time[piv].clear(); for(int i=1; i<=M; i++){ d[piv][i]=-1; } } for(int cnt=0; cnt<K; cnt++){ int from, to, cost, time; ifp>>from>>to>>cost>>time; //scanf("%d %d %d %d", &from, &to, &cost, &time); outflow_time[from].push_back(make_pair(to, time)); outflow_cost[from].push_back(make_pair(to, cost)); } typedef priority_queue<Prove, vector<Prove >, mycomparison> mypq; mypq pq; Prove p(1, 0, 0); d[1][0]=0; pq.push(p); while(!pq.empty()){ Prove front = pq.top(); pq.pop(); int time = front.time; int pos = front.pos; int cost = front.cost; if(d[pos][cost]!=-1 && time > d[pos][cost]) continue; for(int piv=0; piv<outflow_cost[pos].size(); piv++){ int next = outflow_cost[pos][piv].first; int newcost = cost + outflow_cost[pos][piv].second; int newtime = time + outflow_time[pos][piv].second; if(newcost > M) continue; if(d[next][newcost]==-1){ d[next][newcost] = newtime; Prove tmp(next, newcost, newtime); pq.push(tmp); } else if(newtime < d[next][newcost]){ d[next][newcost] = newtime; Prove tmp(next, newcost, newtime); pq.push(tmp); } } } int res=-1; for(int i=1; i<=M; i++){ if(d[N][i]>0){ if(res==-1) res = d[N][i]; else res = min(res, d[N][i]); } } if(res==-1) printf("Poor KCM\n"); else printf("%d\n", res); } return 0; }