[Codeforces] 721C. Journey

題目連結:http://codeforces.com/problemset/problem/721/C

---

莫名其妙吃了MLE，只好把int改short, long long改int = =
本題的做法滿DP的，我狀態直接訂成$dp[i][j]$代表起點到$i$號節點，經過$j$個中繼點所需的最短時間，而DP的順序就按照圖的拓樸排序順序DP就可以好好DP了，不過要注意的是起點有可能不會是拓樸排序的第一個點，所以要稍微判一下...

#include <cstdio>
#include <vector>
#include <utility>
#include <stack>
#include <queue>
using namespace std;
typedef long long lld;
#define PB push_back
typedef pair<short,int> PSI;
typedef pair<short,short> PSS;
#define FF first
#define SS second
const int N = 5000 + 5;
const int INF = 1<<30;

short in[N];
int dp[N][N];
PSS ori[N][N];
vector<PSI> G[N];

int main(){
	short n, m;int t; scanf("%hd%hd%d",&n,&m,&t);
	fill(dp[0], dp[n]+n+1, INF);
	for(int i=0;i<m;i++){
		short u, v; int c; scanf("%hd%hd%d",&u,&v,&c);
		G[u].PB({v, c});
		in[v]++;
	}
	queue<short> qq;
	for(int i=1;i<=n;i++) if(in[i]==0){
		ori[i][1] = {-1, -1};
		dp[i][1] = 0;
		qq.push(i);
	}
	// ori[1][1] = {-1, -1};
	while(!qq.empty()){
		int u = qq.front(); qq.pop();
		for(auto i: G[u]){
			short v = i.FF; int c = i.SS;
			for(int j=0;j<n;j++){
				if(dp[u][j]+c > t) continue;
				if(dp[v][j+1] > dp[u][j]+c){
					dp[v][j+1] = dp[u][j]+c;
					ori[v][j+1] = {u, j};
				}
			}
			in[v]--;
			if(in[v]==0) qq.push(v);
		}
	}
	PSS ans = {n, -1};
	for(int i=0;i<=n;i++) if(dp[n][i] <= t)
		ans.SS = i;
	stack<short> ss;
	while(ans.FF != 1){
		ss.push(ans.FF);
		ans = ori[ans.FF][ans.SS];
	} 
	ss.push(1);
	printf("%d\n", ss.size());
	while(ss.size() > 1){
		printf("%hd ", ss.top());
		ss.pop();
	}
	printf("%hd\n", ss.top());
	return 0;
}