ACdream 1100 瑶瑶饿了（最短路+dp）

题目链接：
ACdream 1100

题解：
先求出最短路，再$dp$。
求最短路你可以$SPFA$，也可以$Flody$，$O(n^3)$。但用$SPFA$要快。玄学$SPFA$。想起就觉得$mmp..$

所以考虑过程中某一状态的$dp[ i ] [ j ][ k ]$ 。

$dp[ i ] [ 1 ][ k ]$表示在过程中吃了在位置 $i$ 的食物，并消耗时间为 $k$ 时，获得的最大价值。
$dp[i][0][k]$表示在过程中没有吃在位置 $i$ 的食物，并消耗时间为 k <script type="math/tex" id="MathJax-Element-28">k</script> 时，获得的最大价值。

AC代码：

/*
* this code is made by LzyRapx
* Problem: 1100
* Verdict: Accepted
* Submission Date: 2017-06-21 09:57:55
* Time: 36MS
* Memory: 1932KB
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 5e6+10;
const int N = 110;
const int M = 10000;
const int mod = 1e9 + 7;
const int inf = ~0U >> 2;

struct Node
{
    int to, next, w;
}e[M << 1];
int head[N], size;
int n, m, T;
int x[N], w[N], t[N];

int dis[N];
bool flag[N];

void addedge(int from, int to, int w)
{
    e[size].to = to;
    e[size].w = w;
    e[size].next = head[from];
    head[from] = size++;
}
void spfa()
{
    queue<int> q;
    fill(dis, dis + n + 1, inf);
    memset(flag, false, sizeof(flag));
    dis[0] = 0;
    q.push(0);
    while(!q.empty())
    {
        int x = q.front(); 
        q.pop();
        flag[x] = false;
        for(int i = head[x]; ~i; i = e[i].next)
        {
            int to = e[i].to;
            if(dis[to] - dis[x] > e[i].w)
            {
                dis[to] = dis[x] + e[i].w;
                if(!flag[to])
                {
                    flag[to] = true;
                    q.push(to);
                }
            }
        }
    }
}

ll dp[2][1010];
int s;

void DP()
{
    memset(dp, -1, sizeof(dp));
    dp[s][0] = 0;
    for(int i = 1; i <= n; i++)
    {
        s ^= 1;
    //    cout<<"s="<<s<<endl; 
        for(int j = 0; j <= T; j++) dp[s][j] = dp[s ^ 1][j];

        int cur_t = dis[i], cur_w = 0;
        for(int k = 1; k <= x[i]; k++)
        {
            cur_t += t[i];
            cur_w += w[i];
            for(int j = T; j >= cur_t; --j)
            {
                if(dp[s ^ 1][j - cur_t] != -1)
                {
                    dp[s][j] = max(dp[s][j], dp[s ^ 1][j - cur_t] + cur_w);
                }
            }
        }
    }
    ll ans = 0;
   // cout<<"s="<<s<<endl; 
    for(int i = 0; i <= T; i++){
        ans = max(ans, dp[1][i]);   
    }
    cout<<ans<<endl;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d%d", &n, &m, &T);
    for(int i = 1; i <= n; ++i) 
        scanf("%d%d%d", &x[i], &w[i], &t[i]);

    for(int i = 0;i < m; i++)
    {
        int x,y,w;
        scanf("%d%d%d", &x, &y, &w);
        addedge(x, y, w);
    }
    spfa();
    DP();
    return 0;
}