浪里個浪 FZU - 2261

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



em 這個題開始就想到了炒雞源點和炒雞匯點，結果偷懶不寫隊列優化T了，看到網上很多用spfa的，還有用網絡流的大佬，網絡流我還不會，這里附上隊列優化迪杰斯特拉的解法

#include<iostream>
#include<cstdio>
#include<vector>
#include<string.h>
#include<queue>
#include<utility>
#define INF 0x3f3f3f3f

using namespace std;
typedef pair<int,int> P;

struct node
{
    int to,w;
    node(int v,int val):to(v),w(val) {}
};

int n,m;
const int maxn = 100007;
int vis[maxn];
int dist[maxn];
vector<node>g[maxn];

void init()
{

    int a,b,c;
    for(int i=0; i<=n; i++)g[i].clear();
    for(int i=0; i<m; i++)
    {
        scanf("%d%d%d",&a,&b,&c);
        g[a].push_back(node(b,c));
    }
    scanf("%d",&a);
    for(int i=0; i<a; i++)
    {
        scanf("%d",&b);
        g[0].push_back(node(b,0));
    }
    scanf("%d",&a);
    for(int i=0; i<a; i++)
    {
        scanf("%d",&b);
        g[b].push_back(node(n+1,0));
    }
}

void dijkstra(int start)
{
    priority_queue<P,vector<P>,greater<P> >que;
    memset(dist,INF,sizeof(dist));
    dist[start] = 0;
    que.push(P(0,start));
    while(!que.empty())
    {
        P p = que.top();
        que.pop();
        int v = p.second;
        if(dist[v]<p.first)continue;
        for(int i=0; i<g[v].size(); i++)
        {
            node e = g[v][i];
            if(dist[e.to] > dist[v] + e.w)
            {
                dist[e.to] = dist[v] + e.w;
                que.push(P(dist[e.to],e.to));
            }
        }
    }
}

int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        init();
        dijkstra(0);
        printf("%d\n",dist[n+1]);
    }
    return 0;
}

?