Aizu 1311 Test Case Tweaking(spfa变形,dp)
来源：程序员人生 发布时间：2015-03-27 08:21:06 阅读次数：3458次
题目链接：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));
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
