NYOJ 247 虛擬的城市之旅

虛擬的城市之旅

描述

展館是未來城市的縮影，個人體驗和互動是不變的主題。在A國展館通過多維模式和高科技手段，引領參觀者在展示空間踏上一段虛擬的城市之旅。 夢幻國有N個城市和M條道路，每條道路連接某兩個城市。任意兩個城市之間最多只有一條道路直接相連。這M條道路中有一部分為單向通行的道路，一部分為雙向通行的道路。 夢幻國幅員遼闊，各地的資源分布情況各不相同，這就導致了同一種商品在不同城市的價格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。 現在你已踏上一段虛擬的城市之旅。為了給你一個意外收獲，允許你在旅游的同時，利用 X 商品在不同城市中的差價賺回一點旅費，但最多只能交易一次。即,在某個城市買入X 商品，可以走到另外一個城市買掉來獲得旅費。當然，在賺不到差價的情況下，你也可以不進行貿易活動。 設夢幻國N個城市的標號從1~ N，你只能從1 號城市出發，並最終在N 號城市結束自己的旅行。在旅游的過程中，任何城市可以重復經過多次，但不要求經過所有N個城市。 例如：夢幻國有5個大城市，城市的編號和道路連接情況如下圖，單向箭頭表示這條道路為單向通行，雙向箭頭表示這條道路為雙向通行。假設 X 商品在1~5 號城市的價格分別為 4，3，5，6，1。 你可以選擇如下一條線路：1235，並在2 號城市以3 的價格買入X 商品，在3號城市以5 的價格賣出X 商品，賺取的旅費數為2。 你也可以選擇如下一條線路14545，並在第1次到達5號城市時以1的價格買入X 商品，在第2次到達4號城市時以6 的價格賣出X 商品，賺取的旅費數為5。 現在給出N個城市的X 商品價格，M條道路的信息（每條道路所連接的兩個城市的編號以及該條道路的通行情況）。請問你能賺取盡可能多的旅費嗎。

輸入

有多組測試數據（以EOF為文件結束的標志）
每組測試數據的格式如下：
第一行：N M 分別表示城市的數目和道路的數目。
第二行：N個正整數，每兩個整數之間用一個空格隔開，分別表示1到N個城市的商品價格。
接下來 M行，每行有3個正整數，X，Y，Z，每兩個整數之間用一個空格隔開。
如果 Z=1，表示這條道路是城市X到城市Y之間的單向道路；
如果Z=2，表示這條道路為城市X 和城市Y之間的雙向道路。

1≤N≤100000，1≤M≤500000，
1≤X，Y≤N，1≤Z≤2，1≤商品價格≤100。

輸出

輸出1個整數，表示最多能賺取的旅費。如果沒有進行貿易，則輸出0。

樣例輸入

5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2

樣例輸出

5

來源

第三屆河南省程序設計大賽

從s點找到到達每個點的最小值，然後從t點找到達每個點的最大值,
然後做差值即可。因為是判斷是否能到達，所以，必須檢測的點都去入隊。

#include"stdio.h"
#include"string.h"
#include"queue"
using namespace std;
#define max(a,b) (a>b?a:b)
#define min(a,b) (aq;
    int x,i,v;
    int mark1[N],mark2[N];
    memset(mark1,0,sizeof(mark1));
    memset(mark2,0,sizeof(mark2));
    mark1[s]=1;
    mark2[n]=1;
    q.push(s);
    while(!q.empty())
    {
        x=q.front();
        q.pop();
        for(i=head1[x];i!=-1;i=bian[i].next)
        {
            v=bian[i].v;
            a[v]=min(a[v],a[x]);
            if(!mark1[v])
            {
                mark1[v]=1;
                q.push(v);
            }
        }
    }
    q.push(n);
    while(!q.empty())      //從終點原路返回起點，即走反向邊
    {
        x=q.front();
        q.pop();
        for(i=head2[x];i!=-1;i=bian[i].next)
        {
            v=bian[i].v;
            b[v]=max(b[v],b[x]);
            if(!mark2[v])
            {
                mark2[v]=1;
                q.push(v);
            }
        }
    }
    int ans=0;
    for(i=1;i<=n;i++)
    {
        if(mark1[i]&&mark2[i])
        {
            ans=max(ans,b[i]-a[i]);
        }
    }
    return ans;
}
int main()
{
    int n,m,u,v,x,i;
    while(scanf("%d%d",&n,&m)!=-1)
    {
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            b[i]=a[i];  //a[i]記錄最小值，b[i]記錄最大值
        }
        memset(head1,-1,sizeof(head1));
        memset(head2,-1,sizeof(head2));
        e=0;
        while(m--)
        {
            scanf("%d%d%d",&u,&v,&x);
            add(u,v);
            if(x==2)
                add(v,u);
        }
        printf("%d\n",spfa(1,n));
    }
    return 0;
}