1 /* 2 dfs比較好想，就是測試數據的問題，導致在遍歷邊的時候要倒著遍歷才過！ 3 */ 4 #include<iostream> 5 #include<cstdio> 6 #include<cstring> 7 #include<vector> 8 #include<algorithm> 9 #define Max 0x3f3f3f3f 10 using namespace std; 11 12 struct node{ 13 int D; 14 int L, T; 15 node(int D, int L, int T){ 16 this->D=D; 17 this->L=L; 18 this->T=T; 19 } 20 node(){ 21 } 22 }; 23 24 node v[105][1000]; 25 int cnt[105]; 26 int vis[105]; 27 28 int maxCost, R, N, S, D, L, T; 29 int cost, dist; 30 31 void dfs(int cur, int d, int c){ 32 int i; 33 if(cur == N){ 34 if(dist>d){ 35 dist=d; 36 if(cost>c) cost=c; 37 } 38 return ; 39 } 40 for(i=cnt[cur]-1; i>=0; --i) 41 if(!vis[v[cur][i].D] && c+v[cur][i].T<=maxCost && d+v[cur][i].L<dist){ 42 vis[v[cur][i].D]=1; 43 dfs(v[cur][i].D, d+v[cur][i].L, c+v[cur][i].T); 44 vis[v[cur][i].D]=0; 45 } 46 } 47 48 int main(){ 49 while(scanf("%d", &maxCost)!=EOF){ 50 scanf("%d%d", &N, &R); 51 memset(cnt, 0, sizeof(cnt)); 52 while(R--){ 53 scanf("%d%d%d%d", &S, &D, &L, &T); 54 v[S][cnt[S]++]=node(D, L, T); 55 } 56 cost=dist=Max; 57 memset(vis, 0, sizeof(vis)); 58 dfs(1, 0, 0); 59 if(cost<=maxCost) 60 printf("%d\n", dist); 61 else printf("-1\n"); 62 } 63 return 0; 64 }
1 /* 2 spfa + 01背包 3 dist[next][j]=min(dist[cur][j-v[cur][i].T]+v[cur][i].L) j={v[cur][i].T。。。maxCost} 4 一維數組表示的是城市節點，二維表示的當前費用 5 dist[i][j]表示經過i城市，費用為j時總的路徑長度！ 6 */ 7 #include<iostream> 8 #include<cstdio> 9 #include<cstring> 10 #include<vector> 11 #include<queue> 12 #include<algorithm> 13 #define Max 0x3f3f3f3f 14 using namespace std; 15 16 struct node{ 17 int D; 18 int L, T; 19 node(int D, int L, int T){ 20 this->D=D; 21 this->L=L; 22 this->T=T; 23 } 24 node(){ 25 } 26 }; 27 28 node v[105][1000]; 29 int cnt[105]; 30 int dist[105][10005]; 31 int vis[105]; 32 queue<int>q; 33 int maxCost, R, N, S, D, L, T; 34 35 int spfa(){ 36 int i; 37 while(!q.empty()){ 38 int cur = q.front(); 39 q.pop(); 40 vis[cur]=0; 41 for(i=0; i<cnt[cur]; ++i){ 42 int next=v[cur][i].D; 43 for(int j=v[cur][i].T; j<=maxCost; ++j) 44 if(dist[next][j]>dist[cur][j-v[cur][i].T]+v[cur][i].L){ 45 dist[next][j]=dist[cur][j-v[cur][i].T]+v[cur][i].L; 46 if(!vis[next]){ 47 vis[next]=1; 48 q.push(next); 49 } 50 } 51 } 52 } 53 } 54 55 void bfs(int cur){ 56 q.push(1); 57 memset(dist, 0x3f, sizeof(dist)); 58 for(int i=0; i<105; ++i) 59 dist[1][i]=0; 60 vis[1]=1; 61 spfa(); 62 } 63 64 int main(){ 65 while(scanf("%d", &maxCost)!=EOF){ 66 scanf("%d%d", &N, &R); 67 memset(cnt, 0, sizeof(cnt)); 68 while(R--){ 69 scanf("%d%d%d%d", &S, &D, &L, &T); 70 v[S][cnt[S]++]=node(D, L, T); 71 } 72 memset(vis, 0, sizeof(vis)); 73 bfs(1); 74 int minDist=Max; 75 for(int i=1; i<=maxCost; ++i) 76 if(minDist>dist[N][i]) 77 minDist=dist[N][i]; 78 if(minDist!=Max) 79 printf("%d\n", minDist); 80 else printf("-1\n"); 81 } 82 return 0; 83 }
?
?
?
...)
)
)
