Aizu 1311 Test Case Tweaking(spfa變形,dp)
來源：程序員人生 發布時間：2015-03-27 08:21:06 閱讀次數：3615次
題目鏈接：http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1311
題意： 給出1張有向圖，和1個權值c，問將1~n亮點之間的最短路徑花費降到c，最少需要修改多少條邊。 數據范圍是100個點,1000條邊。
思路：這道題題目的最關鍵點就是想到用1個2維數據去記錄每一個點的情況（也就是dp式子的定義） dp[x][y] 表示從頂點1動身到達頂點x且修改邊的數量為y時的最小花費（默許修改邊權的時候把邊權直接降為0）， 轉移的時候就是斟酌兩種情況： 修改邊權 和 不修改邊權 （當花費加上邊權大于c的時候1定要修改邊權）。 并且要注意在轉移的進程中，要隨時保證花費是小于c的。
code:
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1005;
vector<pair<int,int> > P[maxn];
int dp[105][maxn],n,m,c;
bool vis[105][maxn];
int spfa(int org)
{
memset(dp,63,sizeof dp);
memset(vis,0,sizeof vis);
queue<pair<int,int> > que;
dp[org][0]=0;
que.push(make_pair(org,0));
vis[org][0]=true;
while(que.size()){
int v=que.front().first;
int nv=que.front().second; que.pop();
if(nv>m) continue; //1定要有
for(int i=0;i<P[v].size();i++){
int u=P[v][i].first,cc=P[v][i].second;
//枚舉兩種轉移方式
if(dp[v][nv]<dp[u][nv+1]){
dp[u][nv+1]=dp[v][nv];
if(!vis[u][nv+1]) que.push(make_pair(u,nv+1));
}
if(dp[v][nv]+cc<=c&&dp[v][nv]+cc<dp[u][nv]){
dp[u][nv]=dp[v][nv]+cc;
if(!vis[u][nv]) que.push(make_pair(u,nv));
}
}
vis[v][nv]=false;
}
for(int i=0;i<=m;i++)
if(dp[n][i]<inf) return i;
}
int main()
{
//freopen("input.txt","r",stdin);
int st,ed,cc;
while(scanf("%d%d%d",&n,&m,&c),n!=0||m!=0||c!=0){
for(int i=0;i<=n;i++) P[i].clear();
for(int i=0;i<m;i++){
scanf("%d%d%d",&st,&ed,&cc);
P[st].push_back(make_pair(ed,cc));
}
printf("%d
",spfa(1));
}
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
