soj 12647. Sightseeing

12647. Sightseeing

Constraints

Time Limit: 20 secs, Memory Limit: 256 MB

Description

A travel agent wants to organize a sightseeing trip in a city for tourists. The city can be modelled as a connected graph, where each node represents a tourist site, and each edge represents a two-way road. Unfortunately, not all roads are good; some roads may be bad due to traffic jam. The agent does not want to disappoint the tourists by visiting the bad roads, and hence wants to compute the best path to take. He assigns a quality value to each road in such a way that a better road has a higher quality value. He also defines the quality value of a path to be the minimum quality among all roads along the path. The following figure depicts an example of 4 tourist sites and 4 roads modelled as a graph.

Each edge in the graph is associated with a value which represents the quality of the road. For e.g. the edge (1, 2), which represents the road connecting node 1 and 2, has quality 10; while the edge (3, 4) has quality 5. The quality of path 1-2-4 is the minimum among the two edges (1, 2) and (2, 4) and thus is min{10, 20} = 10. Likewise, the quality of path 1-2-4-3 is the minimum among the three edges (1, 2), (2, 4) and (3, 4), which is min{10, 20, 5} = 5. Node 1 is the hotel where the tourists stay. Given a destination X, the travel agent wants to find the highest quality among all possible paths from node 1 to node X.

For instance, suppose they want to visit node 4. In the example above, among all possible paths from node 1 to node 4, the highest quality is achieved by the path 1-2-4, with quality 10. On the other hand, if they want to visit node 3 instead of node 4, the highest quality achievable is 30.

Furthermore, the travel agent is not satisfied in knowing the highest quality for a single destination. He has a list of destinations in mind, and he wants to know the highest quality for each of them. Specifically, when given a list of Q sites X1,X2, . . . ,XQ, he wants to know the highest quality from node 1 to node X1, the high quality from node 1 to node X2, and so on.

Input

The first line in the input contains 3 integers, V , E and Q (V<=500,000, E<=5,000,000, Q<=V-1), which represent the number of tourist sites, the number of edges and the number of destinations respectively. The tourist sites are labelled from 1 to V where node 1 denotes the hotel where the tourists start their trip. Next, it is followed by E lines where each line contains 3 integers, v1, v2, and q, where v1 and v2 denote the sites that the road connects and q denotes the quality of the road (0<=q<=100,000). Next, it is followed by Q lines where each line contains an integer X which represents a destination in the travel agent’s list, and X <> 1 (i.e. the hotel is not in the list).

Output

Your program must write to standard output for each destination an integer which is the highest quality achievable.

Sample Input

Sample Output

30
10

Problem Source

2014年每周一赛第十三场

题意:求1到x的路径，最小的最大

思路：类似最短路，直接spfa，不过spfa会卡，改加了优化的dij就好了

// Problem#: 12647
// Submission#: 3287907
// The source code is licensed under Creative Commons Attribution-NonCommercial-ShareAlike 3.0 Unported License
// URI: http://creativecommons.org/licenses/by-nc-sa/3.0/
// All Copyright reserved by Informatic Lab of Sun Yat-sen University
#include <stdio.h>
#include <math.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <queue>
#define LL long long
#define maxn 500010
#define MAX 5000011
#define INF 0x3f3f3f3f
#define mod 1000000007
using namespace std;

struct node
{
    int u,dis;
    node(){}
    node(int x,int y):u(x),dis(y){}
    bool operator<(const node &s) const{
        return dis < s.dis;
    }
};
int que[maxn],dis[maxn];
int head[maxn],to[MAX*2],val[MAX*2];
int next1[MAX*2] ,top ;
bool vi[maxn] ;
void Unit(int &u,int &v,int &c)
{
    next1[top]=head[u];to[top]=v;
    val[top]=c;head[u]=top++;
}
void spfa(int s)
{
    memset(dis,-1,sizeof(dis)) ;
    memset(vi,0,sizeof(vi)) ;
    dis[s]=INF ;
    int i,v;
    priority_queue<node>q;
    q.push(node(s,dis[s])) ;
    node aa;
    while(!q.empty())
    {
        aa=q.top();q.pop();
        if(vi[aa.u]) continue;
        vi[aa.u]=true;
        for( i = head[aa.u] ; i != -1 ; i = next1[i])
        {
            v=to[i] ;
            if(dis[v]<min(aa.dis,val[i]))
            {
                dis[v]=min(aa.dis,val[i]) ;
                q.push(node(v,dis[v]));
            }
        }
    }
}
int main()
{
    int i,n,m,j,Max;
    int len ,k,q ;
    int u,v,c;
    while(scanf("%d%d%d",&n,&m,&q ) != EOF)
    {
         top=0;
         memset(head,-1,sizeof(head)) ;
         while(m--)
         {
             scanf("%d%d%d",&u,&v,&c) ;
             Unit(u,v,c) ;
             Unit(v,u,c) ;
         }
         spfa(1) ;
         while(q--)
         {
             scanf("%d",&u) ;
             printf("%d
",dis[u]) ;
         }
    }
    return 0 ;

}

View Code