NOIP 2009 향상 팀 최 우수 무역

제목 설명
C. 국유 n 개 대도시 와 m 개 도 로 는 각 도로 가 n 개 도시 중의 한 두 도 시 를 연결한다.임의의 두 도시 사이 에는 최대 한 개의 도로 만 이 직접 연결 되 어 있다.이 m 개 도로 중 일 부 는 단 방향 으로 통행 하 는 도로 이 고 일 부 는 양 방향 으로 통행 하 는 도로 이 며 양 방향 으로 통행 하 는 도 로 는 통계 건수 때 도 1 개 로 집계 된다.C 국 가 는 땅 이 넓 고 각지 의 자원 분포 상황 이 각각 다 르 기 때문에 같은 상품 이 서로 다른 도시 에서 의 가격 이 반드시 같 지 않다.그러나 같은 상품 의 같은 도시 에서 의 매입 가와 판매 가 는 항상 같다.상인 아 룡 이 C 국 을 여행 하 러 왔 다.그 는 같은 상품 이 서로 다른 도시 에서 의 가격 이 다 를 수 있다 는 정 보 를 알 게 된 후에 여행 을 하 는 동시에 상품 이 서로 다른 도시 에서 의 차액 을 이용 하여 여 비 를 조금 벌 기로 결정 했다.C 국 n 개 도시 의 레이 블 을 1 ~ n 으로 설정 하고 아 론 은 1 번 도시 에서 출발 해 n 번 도시 에서 자신의 여행 을 끝내기 로 했다.여행 하 는 과정 에서 모든 도 시 는 여러 번 반복 할 수 있 지만 모든 n 개 도 시 를 거 치 는 것 을 요구 하지 않 는 다.아 론 은 이런 무역 방식 으로 여 비 를 벌 었 다. 그 는 지나 가 는 도 시 를 선택 하여 자신 이 가장 좋아 하 는 상품 인 수정 구 를 구입 하고 그 후에 지나 가 는 다른 도시 에서 이 수정 구 를 팔 아 벌 어 들 인 차액 을 여비 로 삼 았 다.아 론 은 주로 C 개국 을 여행 하기 때문에 그 는 이 무역 을 가장 많이 하기 로 결정 했다. 물론 차액 을 벌 지 못 할 경우 무역 을 할 필요 가 없다.C 국유 5 개 대도 시 를 가정 하면 도시 의 번호 와 도로 연결 상황 은 다음 과 같다. 단 방향 화살 표 는 이 도 로 를 단 방향 통행 이 라 고 표시 하고 양 방향 화살 표 는 이 도 로 를 양 방향 통행 이 라 고 표시 한다.
입력 형식:
첫 번 째 줄 은 두 개의 정수 n 과 m 를 포함 하고 중간 에 하나의 빈 칸 으로 나 누 어 도시 의 수량 과 도로 의 수량 을 나타 낸다.두 번 째 줄 n 개의 정수, 두 개의 정수 사이 에 하나의 빈 칸 으로 나 누 어 레이 블 순서에 따라 이 n 개 도시 의 상품 가격 을 표시 합 니 다.다음 m 줄 은 줄 마다 3 개의 정수, x, y, z 가 있 고 두 개의 정수 사 이 를 빈 칸 으로 분리 합 니 다.만약 z = 1 이 라면 이 도 로 는 도시 x 에서 도시 y 사이 의 단 방향 도로 임 을 나타 낸다.만약 z = 2 라면 이 도 로 는 도시 x 와 도시 y 사이 의 양 방향 도로 임 을 나타 낸다.
출력 형식:
출력 파일 trade. out 은 총 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 

출력 예시:

5

데이터 범위: 데 이 터 를 입력 하면 1 번 도시 가 n 번 도시 에 도착 할 수 있 도록 보장 합 니 다.10% 의 데이터 에 대하 여 1 ≤ n ≤ 6.30% 의 데이터 에 대하 여 1 ≤ n ≤ 100.50% 의 데이터 에 대해 하나의 관광 노선 이 존재 하지 않 고 한 도시 에서 출발 하여 다시 이 도시 로 돌아 갈 수 있다.100% 의 데이터 에 대하 여 1 ≤ n ≤ 100000, 1 ≤ m ≤ 500000, 1 ≤ x, y ≤ n, 1 ≤ z ≤ 2, 1 ≤ 각 도시 수정 구 가격 ≤ 100.
spfa 는 1 번 도시 에서 i 점 까지 겪 은 도시 의 최대 치 와 i 점 에서 n 점 까지 겪 은 도시 의 최소 치 를 두 번 처리 하고 마지막 으로 max 에 가면 됩 니 다.

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int size = 201000;
int n,m;
int head[size],next[size],dist[size];
bool use[size];
struct dc
{
    int f,t;
    bool flag;
}l[size],in[size];
int tot = 1;
void build(int f,int t)
{
    l[tot].t = t;
    next[tot] = head[f];
    head[f] = tot ++;
}
queue < int > q;
int mx[size],mn[size];
void spfa(int s)
{
    for(int i = 1 ; i <= n ; i ++)
        mx[i] = 0;
    mx[s] = dist[s];
    use[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int f = q.front();
        q.pop();
        use[f] = 0;
        for(int i = head[f] ; i ; i = next[i])
        {
            int t = l[i].t;
            if(mx[t] < max(mx[f],dist[t]))
            {
                mx[t] = max(mx[f],dist[t]);
                if(!use[t])
                {
                    use[t] = 1;
                    q.push(t);
                }
            }
        }
    }
}
void spfa0(int s)
{
    for(int i = 1 ; i <= n ; i ++)
        mn[i] = 214748364;
    mn[s] = dist[s];
    use[s] = 1;
    q.push(s);
    while(!q.empty())
    {
        int f = q.front();
        q.pop();
        use[f] = 0;
        for(int i = head[f] ; i ; i = next[i])
        {
            int t = l[i].t;
            if(mn[t] > min(mn[f],dist[t]))
            {
                mn[t] = min(mn[f],dist[t]);
                if(!use[t])
                {
                    use[t] = 1;
                    q.push(t);
                }
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i = 1 ; i <= n ; i ++)
        scanf("%d",&dist[i]);
    for(int i = 1 ; i <= m ; i ++)
    {
        int ins;
        scanf("%d%d%d",&in[i].f,&in[i].t,&ins);
        build(in[i].f,in[i].t);
        if(ins == 2)
            in[i].flag = 1 , build(in[i].t,in[i].f);
    }
    spfa0(1);
    memset(l,0,sizeof(l));
    memset(head,0,sizeof(head));
    memset(next,0,sizeof(next));
    tot = 1;
    for(int i = 1 ; i <= m ; i ++)
    {
        build(in[i].t,in[i].f);
        if(in[i].flag)
            build(in[i].f,in[i].t);
    }
    spfa(n);
    int ans = 0;
    for(int i = 1 ; i <= n ; i ++)
        ans = max(ans,mx[i]-mn[i]);
    cout<<ans;
    return 0;
}