程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> bzoj1663 [Usaco2006 Open]趕集 (最短路)

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

編輯:C++入門知識

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;
}

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved