Problem 2261 浪里个浪

Accept: 40    Submit: 106

Time Limit: 1500 mSec    Memory Limit : 32768 KB

 Problem Description

TonyY是一个喜欢到处浪的男人，他的梦想是带着兰兰姐姐浪遍天朝的各个角落，不过在此之前，他需要做好规划。

现在他的手上有一份天朝地图，上面有n个城市，m条交通路径，每条交通路径都是单行道。他已经预先规划好了一些点作为旅游的起点和终点，他想选择其中一个起点和一个终点，并找出从起点到终点的一条路线亲身体验浪的过程。但是他时间有限，所以想选择耗时最小的，你能告诉他最小的耗时是多少吗？

Input

 

包含多组测试数据。

输入第一行包括两个整数n和m，表示有n个地点，m条可行路径。点的编号为1 - n。

接下来m行每行包括三个整数i, j, cost，表示从地点i到地点j需要耗时cost。

接下来一行第一个数为S，表示可能的起点数，之后S个数，表示可能的起点。

接下来一行第一个数为E，表示可能的终点数，之后E个数，表示可能的终点。

0<S, E≤n≤100000，0<m≤100000，0<cost≤100。

 Output

输出他需要的最短耗时。

 Sample Input

4 4 1 3 1 1 4 2 2 3 3 2 4 4 2 1 2 2 3 4

Sample Output

1 

思路：最短路裸模板题。

AC代码：

#define _CRT_SECURE_NO_DEPRECATE#include 
       
        #include
        
         #include
         
          #include
          
           #include
           
            using namespace std;#define inf 0x3f3f3f3fstruct Edge {    int from, to, dist;    Edge(int u = 0, int v = 0, int w = 0) :from(u), to(v), dist(w) {}};struct HeapNode {    int dist, u;  //顶点u距离s的距离为dist    HeapNode(int w = 0, int x = 0) :dist(w), u(x) {}    bool operator<(const HeapNode&rhs)const {        return dist>rhs.dist;    }};struct Graph {    const static int V = 1e5 + 10+2;    int n, m;    vector
            
             edges; // 边集 vector
             
              G[V]; bool done[V]; //是否已经永久标号 int d[V]; //s到各个顶点的距离 void init(int n) { this->n = n; for (int i = 0; i
              

&s) { memset(d, 0x3f, sizeof(d)); memset(done, 0, sizeof(done)); priority_queue

Q; int ns = s.size(); for (int i = 0; i

d[u] + e.dist) { d[e.to] = d[u] + e.dist; Q.push(HeapNode(d[e.to], e.to)); } } } } int slove(const vector

&s, const vector

&t) { dijkstra(s); int res = inf, nt = t.size(); for (int i = 0; i

s, t;int main() { //源点0，汇点n+1 //freopen("in.txt","r",stdin); int n, m, u, v, w, S, E; while (scanf("%d %d", &n, &m) == 2) { slover.init(n + 2); s.clear(), t.clear(); for (int i = 0; i