国内最全IT社区平台 联系我们 | 收藏本站
华晨云阿里云优惠2
您当前位置:首页 > php开源 > php教程 > Aizu 1311 Test Case Tweaking(spfa变形,dp)

Aizu 1311 Test Case Tweaking(spfa变形,dp)

来源:程序员人生   发布时间:2015-03-27 08:21:06 阅读次数:3446次

题目链接: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)); } }


生活不易,码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生
------分隔线----------------------------
分享到:
------分隔线----------------------------
关闭
程序员人生