假設有A，B兩種貨幣，要將A換成B，須透過匯率Rab和手續費Cab，因此實際得到B貨幣=(A-Cab)*Rab元。
第一行輸入N, M, S, V，N表示共有N種貨幣(1<=N<=100)，M表示底下有M行，每一行有六個數字A,B,Rab,Cab,Rba,Cab，Rab表示A換成B的匯率，Cab表示A換成B需要扣除的手續費，Rba和Cba同理。現在Nick有第S種貨幣V元，題目問Nick透過不斷交換貨幣，然後最後換回第S種貨幣的時候能否大於V元?
想法：
用SPFA演算法，初始除了Dis[S]=V以外Dis[i]都是0，然後不斷更新Dis的值使其盡可能大，最後判斷Dis[S]是否大於V。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <cstdio> | |
| #include <queue> | |
| #include <vector> | |
| using namespace std; | |
| int main() | |
| { | |
| int N, M, S; | |
| double V; | |
| double R[101][101] = {0}; | |
| double C[101][101]; | |
| vector<int> toNxt[101]; | |
| // Input | |
| scanf("%d %d %d %lf", &N, &M, &S, &V); | |
| int a, b; double Rab, Rba, Cab, Cba; | |
| for (int i = 0; i < M; ++i) { | |
| scanf("%d %d %lf %lf %lf %lf", &a, &b, &Rab, &Cab, &Rba, &Cba); | |
| R[a][b] = Rab; R[b][a] = Rba; | |
| C[a][b] = Cab; C[b][a] = Cba; | |
| toNxt[a].push_back(b); | |
| toNxt[b].push_back(a); | |
| } | |
| // SPFA | |
| double Dis[101] = {0}; | |
| queue<int> Q; | |
| bool inQueue[101] = {0}; | |
| Dis[S] = V; | |
| Q.push(S); | |
| inQueue[S] = true; | |
| while (!Q.empty()) { | |
| int now = Q.front(); | |
| inQueue[now] = false; | |
| Q.pop(); | |
| for (int i = 0; i < toNxt[now].size(); ++i) { | |
| int nxt = toNxt[now][i]; | |
| if (Dis[nxt] < (Dis[now]-C[now][nxt])*R[now][nxt]) { | |
| Dis[nxt] = (Dis[now]-C[now][nxt])*R[now][nxt]; | |
| if (!inQueue[nxt]) { | |
| Q.push(nxt); | |
| inQueue[nxt] = true; | |
| } | |
| } | |
| } | |
| } | |
| // Analysis & Output | |
| if (Dis[S] > V) puts("YES"); | |
| else puts("NO"); | |
| } |
沒有留言:
張貼留言