bzoj1663 [Usaco2006 Open]趕集 (最短路)

bzoj1663 [Usaco2006 Open]趕集 (最短路)

Description

每一年，約翰都會帶著他的奶牛們去趕集．集會中一共有N(1≤N≤400)個商店，第i個商店會在特定的時間Pi(0≤Pi≤109)對當時在店裡的顧客送出一份精美的禮物．約翰當然得到了這個消息，於是他希望能拿到盡量多的禮物送給他的奶牛們．也就是說，他想盡可能多地在某商店發放禮物的時候，正好呆在店裡．
經過一定的調查，約翰弄清楚了從i號商店走到J號商店所需要的時間Ti,j(1≤Ti,j≤1000000)．雖然鄉間小路奇特的布局使得從i號商店走到j號商店的最短路不一定是直接連接這兩個商店的那條，但約翰並不會選擇那些會經過其他商店的路線，只是直接走到目標商店等待禮物的送出．此外，Ti,j並不一定等於Tj,i，由於約翰爬山的速度總是很慢．
約翰在時間0時於1號商店開始他的旅途．請你幫他設計一條路線來獲得盡可能多的禮物。

Input

第1行輸入一個正整數N．接下來N行每行一個整數Pi．
接下來一個n?n的矩陣描述Ti,j

Output

輸出一個整數，即約翰最多能拿到的禮物的個數

Sample Input

4
13 9 19 3
0 10 20 3
4 0 11 2
1 15 0 12
5 5 13 0

Sample Output

3

Hint

一共有4家商店．1號商店會在時間13送出一份禮物，2號商店送出禮物的時間為9，3號商店是時間19，4號商店是時間3． 約翰先在時間3走到4號商店，正好拿到送出的禮物．然後他再直接走到2號商店（不經過任何中轉商店），在時間8到那兒，然後等待1單位時間，在時間9拿到商店送出的禮物後馬上出發去1號商店，又正好能在時間13到達並拿到第3份禮物．

Source

Gold

---

Solution

將點按照出現時間排好序 如果從i點能到達j點則從i向j連一條邊。
從i點能到達j點是指：取完i點的物品後，直接走向j點，能在j點物品下落之前到達，即p[i]+Ti,j<=p[j]。 方便起見，我們假設出發點為0，p[0]=0,T0,i=T1,i。 跑一邊spfa求出0到其他點的最長路，其中最長的就是答案。

今天才發現，溫少BZOJ200+啦~~~~orz。。

#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

int n;
struct Node{
    int pos, tim;
    bool operator < (const Node &n) const {
        return tim < n.tim;
    }
}p[405];
int d[405][405];
vector edges[405];
int dist[405];
bool vis[405];

int spfa() {
    queue q;
    q.push(0);
    vis[0] = 1;
    while (!q.empty()) {
        int current = q.front();
        q.pop();
        for (int i = 0; i < edges[current].size(); i++) {
            if (dist[current] + 1 > dist[edges[current][i]]) {
                dist[edges[current][i]] = dist[current] + 1;
                if (!vis[edges[current][i]]) {
                    vis[edges[current][i]] = 1;
                    q.push(edges[current][i]);
                }
            }
        }
        vis[current] = 0;
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        ans = max(ans, dist[i]);
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &p[i].tim);
        p[i].pos = i;
    }
    sort(p + 1, p + n + 1);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &d[i][j]);
    for (int i = 1; i <= n; i++)
        d[0][i] = d[1][i];
    p[0].pos = p[0].tim = 0;
    for (int i = 0; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (p[i].tim + d[p[i].pos][p[j].pos] <= p[j].tim)
                edges[i].push_back(j);
    int ans = spfa();
    printf("%d\n", ans);
    return 0;
}