Vijos - 最優貿易(雙向Spfa)

題目連結:https://vijos.org/p/1754

題目描述

C 國有 n 個大城市和 m 條道路，每條道路連接配接這 n 個城市中的某兩個城市。任意兩個

城市之間最多隻有一條道路直接相連。這 m 條道路中有一部分為單向通行的道路，一部分

為雙向通行的道路，雙向通行的道路在統計條數時也計為 1 條。 

C 國幅員遼闊，各地的資源分布情況各不相同，這就導緻了同一種商品在不同城市的價

格不一定相同。但是，同一種商品在同一個城市的買入價和賣出價始終是相同的。 

商人阿龍來到 C 國旅遊。當他得知同一種商品在不同城市的價格可能會不同這一資訊

之後，便決定在旅遊的同時，利用商品在不同城市中的差價賺回一點旅費。設 C 國 n 個城

市的标号從 1~ n，阿龍決定從 1 号城市出發，并最終在 n 号城市結束自己的旅行。在旅遊的

過程中，任何城市可以重複經過多次，但不要求經過所有 n 個城市。阿龍通過這樣的貿易方

式賺取旅費：他會選擇一個經過的城市買入他最喜歡的商品——水晶球，并在之後經過的另

一個城市賣出這個水晶球，用賺取的差價當做旅費。由于阿龍主要是來 C 國旅遊，他決定

這個貿易隻進行最多一次，當然，在賺不到差價的情況下他就無需進行貿易。 

假設 C 國有 5 個大城市，城市的編号和道路連接配接情況如下圖，單向箭頭表示這條道路

為單向通行，雙向箭頭表示這條道路為雙向通行。

假設 1~n 号城市的水晶球價格分别為 4，3，5，6，1。 

阿龍可以選擇如下一條線路：1->2->3->5，并在 2 号城市以 3 的價格買入水晶球，在 3

号城市以 5的價格賣出水晶球，賺取的旅費數為 2。 

阿龍也可以選擇如下一條線路 1->4->5->4->5，并在第 1 次到達 5 号城市時以 1 的價格

買入水晶球，在第 2 次到達 4 号城市時以 6 的價格賣出水晶球，賺取的旅費數為 5。

現在給出 n個城市的水晶球價格，m條道路的資訊（每條道路所連接配接的兩個城市的編号

以及該條道路的通行情況） 。請你告訴阿龍，他最多能賺取多少旅費。

輸入格式

第一行包含 2 個正整數 n 和 m，中間用一個空格隔開，分别表示城市的數目和道路的

數目。 

第二行 n 個正整數，每兩個整數之間用一個空格隔開，按标号順序分别表示這 n 個城

市的商品價格。 

接下來 m行， 每行有 3 個正整數， x， y， z， 每兩個整數之間用一個空格隔開。 如果 z=1，

表示這條道路是城市 x到城市 y之間的單向道路；如果 z=2，表示這條道路為城市 x 和城市

y之間的雙向道路。

輸出格式

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

則輸出 0。

樣例輸入

5 5 

4 3 5 6 1 

1 2 1 

1 4 1 

2 3 2 

3 5 1 

4 5 2 

樣例輸出

限制

解題思路

#include <queue>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define N 100010
using namespace std;
const int inf = 1e8;
struct edge {
    int u, v;
}e[2][N * 10];
int f[2][N], val[N], mins[N], maxs[N], vis[N], cnt, ans, n, m;
void Add(int u, int v)
{
    e[0][++cnt] = (edge){f[0][u], v};
    f[0][u] = cnt;
    e[1][cnt] = (edge){f[1][v], u};
    f[1][v] = cnt;
}
void init()
{
    for (int i = 1; i <= n; i++)
    {
        maxs[i] = -1;
        mins[i] = inf;
    }
}
void Spfa_1(int s)
{
    queue <int> Q;
    Q.push(s);
    vis[s] = 1;
    mins[s] = val[s];
    while (!Q.empty())
    {
        int t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int j = f[0][t]; j; j = e[0][j].u)
        {
            int v = e[0][j].v;
            if (mins[v] > mins[t] || mins[v] > val[v])
            {
                mins[v] = min(mins[t], val[v]);
                if (!vis[v])
                {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
void Spfa_2(int s)
{
    queue <int> Q;
    Q.push(s);
    vis[s] = 1;
    maxs[s] = val[s];
    while (!Q.empty())
    {
        int t = Q.front();
        Q.pop();
        vis[t] = 0;
        for (int j = f[1][t]; j; j = e[1][j].u)
        {
            int v = e[1][j].v;
            if (maxs[v] < maxs[t] || maxs[v] < val[v])
            {
                maxs[v] = max(maxs[t], val[v]);
                ans = max(maxs[v] - mins[v], ans);
                if (!vis[v])
                {
                    Q.push(v);
                    vis[v] = 1;
                }
            }
        }
    }
}
int main()
{
    int x, y, z;
    while (~scanf("%d%d", &n, &m))
    {
        cnt = 0;
        init();
        memset(f, 0, sizeof(f));
        for (int i = 1; i <= n; i++)
            scanf("%d", &val[i]);
        for (int i = 0; i < m; i++)
        {
            scanf("%d%d%d", &x, &y, &z);
            Add(x, y);
            if (z == 2)
                Add(y, x);
        }
        ans = -1;
        Spfa_1(1);
        Spfa_2(n);
        printf("%d\n", ans);
    }
    return 0;
}