原題及翻譯

ROADS

路
Time Limit: 1000MS
時間限制：1000ms
Memory Limit: 65536K
內存限制：65536k
Total Submissions: 19213
總提交：19213
Accepted: 6804
通過：6804
Description
描述
N cities named with numbers 1 … N are connected with one-way roads.
N個城市，分別是1……N它們之間有單向連通的道路。
Each road has two parameters associated with it : the road length and the toll that needs to be paid for the road (expressed in the number of coins).
每路有兩個參數：長度與它的過路費（支付需要的是那條路的硬幣中的數量）。
Bob and Alice used to live in the city 1.
Bob和Alice過去常常住在1城市。
After noticing that Alice was cheating in the card game they liked to play, Bob broke up with her and decided to move away - to the city N.
在他注意到愛麗絲喜歡卡片游戲后，鮑勃決定了去城市N。
He wants to get there as quickly as possible, but he is short on cash.
他想盡快到達但是他沒有足夠的現金。
We want to help Bob to find the shortest path from the city 1 to the city N that he can afford with the amount of money he has.
我們要找到最短的路徑來幫助鮑勃從1城市到N城市，并且以他能負擔得起一個金額。

Input

輸入
The first line of the input contains the integer K, 0 <= K <= 10000, maximum number of coins that Bob can spend on his way.
第一行輸入線的整數k，0≤k≤10000，是鮑勃所有的錢。
The second line contains the integer N, 2 <= N <= 100, the total number of cities.
第二行是整數n，2≤N≤100，總數量的城市。
The third line contains the integer R, 1 <= R <= 10000, the total number of roads.
第三行是整數R，1≤R≤10000，總數量的道路。
Each of the following R lines describes one road by specifying integers S, D, L and T separated by single blank characters :
每個R線以下介紹一道由指定的單空白字符分隔的D，L和S，T：
S is the source city, 1 <= S <= N
S是出發城市，1 <= S <= N
D is the destination city, 1 <= D <= N
D是目的城市，1 <= D <= N
L is the road length, 1 <= L <= 100
L是道長，1 <= L <= 100
T is the toll (expressed in the number of coins), 0 <= T <=100
T是收費（以硬幣的數量表示），0 <= T <=100
Notice that different roads may have the same source and destination cities.
注意，不同的道路可能有相同的起點和目的地城市。

Output

輸出
The first and the only line of the output should contain the total length of the shortest path from the city 1 to the city N whose total toll is less than or equal K coins.
只有一個輸出，應包含最短路徑的總長度從1到n的最大城市，總金額是小于或等于k的硬幣。
If such path does not exist, only number -1 should be written to the output.
如果這樣的路徑不存在，輸出數字-1。
Sample Input
5
6
7
1 2 2 3
2 4 3 3
3 4 2 4
1 3 4 1
4 6 2 1
3 5 2 0
5 4 3 2
Sample Output
11
Source
CEOI 1998

解題思路

從城市1開始深度優先遍歷整個圖，找到所有能過到達N的走法，選一個最優的。

但是，直接這樣遍歷是會超時的，這就需要對程序進行優化剪枝。

最優性剪枝：

1.如果當前已經找到的最優路徑程度為L，那么在繼續搜索的過程中，總長度已經大于等于L的走法就可以直接放棄，不用走到底了。
保存中間值的最優性剪枝。

2.用mid[k][m]表示：走到城市k時總過路費為m的條件下，最優路徑的長度。若在后續的搜索中，再次走到k時，如果總路費恰好為m，且此時的最優長度已經超過mid[k][m]，則不必再走下去了。

代碼分析

1.可以用鏈接表存儲城市的數據，先聲明一個城市道路的結構，然后創建一個Road類型的鏈接表cityMap：

struct Road {int d,L,t; }; vector<vector<Road> > cityMap(110);

2.然后創建需要的幾個全局變量（表示當前找到的最優路徑長度minLen，初始化為一個很大的值、表示正在走的路徑的長度totalLen、表示走過路徑的總花銷totalCost、用于標記城市是否走過的數組visited[110]、還有用于表示從1到某個城市最短路徑的長度的花銷minL[110][10100]）：

int K,N,R; int minLen = 1 << 30; int totalLen=0; int totalCost=0; int visited[110]; int minL[110][10100];

3.接下來寫主函數，用于讀入和處理數據以及調用函數還有結果的輸出：

int main() {cin >>K >> N >> R;//讀入K（鮑勃所有的錢），N（城市的總數量），R（道路的總數量）for( int i = 0;i < R; ++ i){int s;//城市的序號Road r;//Road類型的變量rcin >> s >> r.d >> r.L >> r.t;//讀入出發城市的序號、目的城市的序號、道長和過路費。if( s != r.d )//排除只有一個城市的情況cityMap[s].push_back(r);//將r添加到cityMap中}for( int i = 0;i < 110; ++i )for( int j = 0; j < 10100; ++ j )minL[i][j] = 1 << 30;memset(visited,0,sizeof(visited));//先將所有的城市都標記為0visited[1] = 1;//然后把第一個城市標記為1Dfs(1);//調用深度搜索函數if( minLen < (1 << 30))//如果有比極大值小的路徑則輸出cout << minLen << endl;else//如果沒有則輸出-1cout << "-1" << endl; }

4.最后就是主角登場了，深度搜索函數：

void Dfs(int s) {//從s開始向N行走if(s==N){//如果到達終點，返回當前總路徑和最短路徑。minLen = min(minLen,totalLen);return ;}for(int i=0;i<cityMap[s].size();++i ){//遍歷cityMap的所有元素int d=cityMap[s][i].d; //s有路連到dif(! visited[d] ){//確定d城市沒有走過int cost=totalCost+cityMap[s][i].t;//計算當前花銷if(cost>K) continue; //可行性剪枝//如果花銷大于總金額，直接跳過。if(totalLen+cityMap[s][i].L>=minLen||totalLen+cityMap[s][i].L>=minL[d][cost]) continue;//如果當前總路徑>=之前走過該城市時的路徑，直接跳過。totalLen+=cityMap[s][i].L;totalCost+=cityMap[s][i].t;minL[d][cost] = totalLen;visited[d] = 1;//累加所有的數據并標價城市為1Dfs(d);//從當前位置出發往N走visited[d]=0;totalCost-=cityMap[s][i].t;totalLen-=cityMap[s][i].L;//如果不能到達N或者條件不允許，退回。}} }

完整代碼

#include <iostream> #include <vector> #include <cstring> using namespace std; int K,N,R; struct Road {int d,L,t; }; vector<vector<Road> > cityMap(110); int minLen=1<<30; int totalLen=0; int totalCost=0; int visited[110]; int minL[110][10100]; void Dfs(int s) {if( s == N ){minLen = min(minLen,totalLen);return ;}for( int i = 0 ;i < cityMap[s].size(); ++i ){int d = cityMap[s][i].d;if(! visited[d] ){int cost = totalCost + cityMap[s][i].t;if( cost > K) continue;if( totalLen + cityMap[s][i].L >= minLen ||totalLen + cityMap[s][i].L >= minL[d][cost]) continue;totalLen += cityMap[s][i].L;totalCost += cityMap[s][i].t;minL[d][cost] = totalLen;visited[d] = 1;Dfs(d);visited[d] = 0;totalCost-= cityMap[s][i].t;totalLen-= cityMap[s][i].L;}} } int main() {cin >>K >> N >> R;for( int i = 0;i < R; ++ i){int s;Road r;cin >> s >> r.d >> r.L >> r.t;if( s != r.d )cityMap[s].push_back(r);}for(int i=0;i<110;++i)for(int j=0;j<10100;++j)minL[i][j]=1<<30;memset(visited,0,sizeof(visited));visited[1] = 1;minLen = 1 << 30;Dfs(1);if( minLen < (1 << 30))cout << minLen << endl;elsecout << "-1" << endl; }

總結

以上是生活随笔為你收集整理的百练1724:ROADS的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。