拓扑序+dp Codeforces Round #374 (Div. 2) C

http://codeforces.com/contest/721/problem/C

题目大意:给你有向路,每条路都有一个权值t,你从1走到n,最多花费不能超过T,问在T时间内最多能访问多少城市?

思路:dp确实好玩,然而我不会TAT

首先我们定义dp[i][j]表示从i走到n,途中经过j个城市所需要的花费。接下来就枚举拓扑序就好了

//看看会不会爆int!数组会不会少了一维!
//取物问题一定要小心先手胜利的条件
#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define ALL(a) a.begin(), a.end()
#define pb push_back
#define mk make_pair
#define fi first
#define se second
#define haha printf("haha\n")
const int maxn = + ;
vector<pair<int, int> > G[maxn];
int n, m, T;
bool vis[maxn];
int par[maxn][maxn], dp[maxn][maxn];
///定义从i走到n,经过j个地方所需要的最小时间花费 void dfs(int u){
vis[u] = true;
int len = G[u].size();
for (int i = ; i < len; i++){
pair<int, int> p = G[u][i];
int v = p.fi, val = p.se;
if (!vis[v]) dfs(v);
for (int j = ; j <= n; j++){
if (dp[u][j] > dp[v][j - ] + val){
dp[u][j] = dp[v][j - ] + val;
par[u][j] = v;
}
}
}
} int main(){
cin >> n >> m >> T;
memset(dp, 0x3f, sizeof(dp));
dp[n][] = ;
for (int i = ; i <= m; i++){
int u, v, val;
scanf("%d%d%d", &u, &v, &val);
G[u].pb(mk(v, val));
}
memset(par, -, sizeof(par));
dfs();
/*
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
///printf("%d ", dp[i][j]);
printf("%d ", par[i][j]);
}
printf("\n");
}
*/
for (int i = n; i >= ; i--){
if (dp[][i] <= T){
printf("%d\n", i);
for (int j = ; j != -; j = par[j][i], i--){
printf("%d ", j);
}
break;
}
}
return ;
}
上一篇:java学会需要掌握的知识(来源网上。。)


下一篇:Java数组排序和查找