没有什么是一遍搜索解决不了的, 如果有, 那就正反两遍

啧啧啧…

懵逼的 题目

传送至 Luogu

扯淡的 题解

正反两遍bfs就好惹…
从终点bfs, 求出[终点到每个点 路途中的最大价格]
从起点bfs, 求出[起点到每个点 路途中的最小价值]
注意两点:

  • 最小值最大值的初始化, 因为可能有[起点可以到达但不能到达终点的点] || [可以到达终点但不能从起点达到的点]
  • 边的条数, 题目中的m不是边的条数而是输入的行数, 边还是应该开m << 1垃圾题目

沙茶的 代码

话说有什么好的[反向建图, 从终点bfs]的写法嘛…感觉好丑TUT

// noip2009T3.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstring>
#include <algorithm>
#include <queue>
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
    int from;
    int to;
    int next;
}b[MAXM << 1], bf[MAXN << 1];
int cntb = 0;
int cntbf = 0;
int g[MAXN];
int gf[MAXN];

struct node
{
    int minc;
    int maxc;
}a[MAXN];

struct qnode
{
    int bh;
    int zhi;
    qnode(int b, int z): bh(b), zhi(z) {}
};
int n;
int m;
int ans;
int val[MAXN];
void bfs0(int);
void bfs1(int);
void adn(int, int);
void adnf(int, int);
void solve();
int main()
{
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> val[i];
        a[i].maxc = 0;
        a[i].minc = INF;
    }
    int srx, sry, srz;
    for (int i = 1; i <= m; i++)
    {
        cin >> srx >> sry >> srz;
        if (srz == 1)
        {
            adn(srx, sry);
            adnf(sry, srx);
        }
        else
        {
            adn(srx, sry);
            adn(sry, srx);
            adnf(srx, sry);
            adnf(sry, srx);
        }
    }
    solve();
    cout << ans;
    return 0;
}
void adn(int from, int to)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    g[from] = cntb;
}
void adnf(int from, int to)
{
    bf[++cntbf].next = gf[from];
    bf[cntbf].from = from;
    bf[cntbf].to = to;
    gf[from] = cntbf;
}
void solve()
{
    bfs0(1);
    bfs1(n);
    for (int i = 1; i <= n; i++)
    {
        ans = max(ans, a[i].maxc - a[i].minc);
    }
}
void bfs0(int startDash)
{
    int v[MAXN];
    memset(v, 0, sizeof(v));
    queue<qnode> q;
    q.push(qnode(startDash, val[startDash]));
    v[startDash] = 1;
    while (!q.empty())
    {
        qnode dq = q.front();    q.pop();
        a[dq.bh].minc = min(a[dq.bh].minc, dq.zhi);
        if (v[dq.bh] >= 2)
            continue;
        v[dq.bh]++;
        for (int i = g[dq.bh]; i; i = b[i].next)
        {
            if (v[b[i].to] < 2)
            {
                q.push(qnode(b[i].to, min(val[b[i].to], dq.zhi)));
            }
        }
    }
}
void bfs1(int startDash)
{
    int v[MAXN];
    memset(v, 0, sizeof(v));
    queue<qnode> q;
    q.push(qnode(startDash, val[startDash]));
    v[startDash] = 1;
    while (!q.empty())
    {
        qnode dq = q.front();    q.pop();
        a[dq.bh].maxc = max(a[dq.bh].maxc, dq.zhi);
        if (v[dq.bh] >= 2)
            continue;
        v[dq.bh]++;
        for (int i = gf[dq.bh]; i; i = bf[i].next)
        {
            if (v[bf[i].to] < 2)
            {
                q.push(qnode(bf[i].to, max(val[bf[i].to], dq.zhi)));
            }
        }
    }
}

/*
5 5
4 3 5 6 1
1 2 1
1 4 1
2 3 2
3 5 1
4 5 2
*/

By 被D飞的 Cansult