Cycling

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Total Submission(s): 105 Accepted Submission(s): 49

Problem Description

You want to cycle to a programming contest. The shortest route to the contest might be over the tops of some mountains and through some valleys. From past experience you know that you perform badly in programming contests after experiencing large differences in altitude. Therefore you decide to take the route that minimizes the altitude difference, where the altitude difference of a route is the difference between the maximum and the minimum height on the route. Your job is to write a program that finds this route.
You are given:

the number of crossings and their altitudes, and

the roads by which these crossings are connected.
Your program must find the route that minimizes the altitude difference between the highest and the lowest point on the route. If there are multiple possibilities, choose the shortest one.
For example:

In this case the shortest path from 1 to 7 would be through 2, 3 and 4, but the altitude difference of that path is 8. So, you prefer to go through 5, 6 and 4 for an altitude difference of 2. (Note that going from 6 directly to 7 directly would have the same difference in altitude, but the path would be longer!)

Input

On the first line an integer t (1 <= t <= 100): the number of test cases. Then for each test case:

One line with two integers n (1 <= n <= 100) and m (0 <= m <= 5000): the number of crossings and the number of roads. The crossings are numbered 1..n.

n lines with one integer hi (0 <= h_i <= 1 000 000 000): the altitude of the i-th crossing.

m lines with three integers a_j , b_j (1 <= a_j , b_j <= n) and c_j (1 <= c_j <= 1 000 000): this indicates that there is a two-way road between crossings a_j and b_j of length c_j . You may assume that the altitude on a road between two crossings changes linearly.
You start at crossing 1 and the contest is at crossing n. It is guaranteed that it is possible to reach the programming contest from your home.

Output

For each testcase, output one line with two integers separated by a single space:

the minimum altitude difference, and

the length of shortest path with this altitude difference.

Sample Input

Sample Output

2 11

Source

bapc2007_pre

Recommend

lcy

/*
题意：小明上学，从1到n，每个点都有高度，让你找出来一条高度差最小，这个条件下的最短路

初步思路：将所有的高度差计算出来，然后排序，从小到大找到第一个，能找到最短路的输出

#问题：很奇怪计算高度差的时候还要考虑和自身的高度差
*/
#include<bits/stdc++.h>
using namespace std;
struct Point{
    int low,high;
    Point(){}
    Point(int a,int b){
        low=a;
        high=b;
    }
    bool operator < (const Point & b) const{
        return (high-low)<(b.high-b.low);
    }
};
int t;
int n,m;
int h[110];
Point difference_h[110*110];
int u,v,val;
int tol=0;
/*****************************************************spaf模板*****************************************************/
const int MAXN = 1010;
const int INF = 0x3f3f3f3f;
struct Edge {
    int v;
    int cost;
    Edge(int _v = 0, int _cost = 0) :
            v(_v), cost(_cost) {
    }
};
vector<Edge> E[MAXN];
void addedge(int u, int v, int w) {
    E[u].push_back(Edge(v, w));
    E[v].push_back(Edge(u, w));
}
bool vis[MAXN]; //在队列标志
int cnt[MAXN]; //每个点的入队列次数
int dist[MAXN];
bool SPFA(int start, int n,int low,int high) {
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= n; i++)
        dist[i] = INF;
    vis[start] = true;
    dist[start] = 0;
    queue<int> que;
    while (!que.empty())
        que.pop();
    que.push(start);//将第一个点放进队列
    memset(cnt, 0, sizeof(cnt));
    cnt[start] = 1;//标记一下这个点第一次进入队列中
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        if(h[u]<low||h[u]>high)//控制高度差   
            continue; 
        vis[u] = false;
        for (int i = 0; i < E[u].size(); i++) {//遍历他所有能链接到的边
            int v = E[u][i].v;
            if (h[v]>=low&&h[v]<=high&&dist[v] > dist[u] + E[u][i].cost) {//进行缩点
                dist[v] = dist[u] + E[u][i].cost;
                if (!vis[v]) {//这个点没有访问过
                    vis[v] = true;
                    que.push(v);
                    if (++cnt[v] > n)
                        return false;      //cnt[i]为入队列次数，用来判定是否存在负环回路
                }
            }
        }
    }
    return true;
}
/*****************************************************spaf模板*****************************************************/
void init(){
    for(int i=0;i<=n;i++){
        E[i].clear();
    }
    tol=0;
}
int main(){
    // freopen("in.txt","r",stdin);
    scanf("%d",&t);
    while(t--){
        scanf("%d%d",&n,&m);
        init();
        for(int i=1;i<=n;i++){
            scanf("%d",&h[i]);
        }
        for(int i=0;i<m;i++){
            scanf("%d%d%d",&u,&v,&val);
            //建图
            addedge(u,v,val);
        }
        // cout<<"ok"<<endl;
        for(int i=1;i<=n;i++){
            for(int j=i;j<=n;j++){
                difference_h[tol].low=min(h[i],h[j]);
                difference_h[tol++].high=max(h[i],h[j]);
            }
        }
        // cout<<"ok"<<endl;
        sort(difference_h,difference_h+tol);
        for(int i=0;i<tol;i++){
            SPFA(1,n,difference_h[i].low,difference_h[i].high);
            if(dist[n]!=INF){
                printf("%d %d
",difference_h[i].high-difference_h[i].low,dist[n]);
                break;
            }
        }
    }
    return 0;
}