TonyY是一個(gè)喜歡到處浪的男人，他的夢(mèng)想是帶著蘭蘭姐姐浪遍天朝的各個(gè)角落，不過(guò)在此之前，他需要做好規(guī)劃。

現(xiàn)在他的手上有一份天朝地圖，上面有n個(gè)城市，m條交通路徑，每條交通路徑都是單行道。他已經(jīng)預(yù)先規(guī)劃好了一些點(diǎn)作為旅游的起點(diǎn)和終點(diǎn)，他想選擇其中一個(gè)起點(diǎn)和一個(gè)終點(diǎn)，并找出從起點(diǎn)到終點(diǎn)的一條路線親身體驗(yàn)浪的過(guò)程。但是他時(shí)間有限，所以想選擇耗時(shí)最小的，你能告訴他最小的耗時(shí)是多少嗎？

Input

?

包含多組測(cè)試數(shù)據(jù)。

輸入第一行包括兩個(gè)整數(shù)n和m，表示有n個(gè)地點(diǎn)，m條可行路徑。點(diǎn)的編號(hào)為1 - n。

接下來(lái)m行每行包括三個(gè)整數(shù)i, j, cost，表示從地點(diǎn)i到地點(diǎn)j需要耗時(shí)cost。

接下來(lái)一行第一個(gè)數(shù)為S，表示可能的起點(diǎn)數(shù)，之后S個(gè)數(shù)，表示可能的起點(diǎn)。

接下來(lái)一行第一個(gè)數(shù)為E，表示可能的終點(diǎn)數(shù)，之后E個(gè)數(shù)，表示可能的終點(diǎn)。

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

Output

輸出他需要的最短耗時(shí)。

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 這個(gè)題開(kāi)始就想到了炒雞源點(diǎn)和炒雞匯點(diǎn)，結(jié)果偷懶不寫(xiě)隊(duì)列優(yōu)化T了，看到網(wǎng)上很多用spfa的，還有用網(wǎng)絡(luò)流的大佬，網(wǎng)絡(luò)流我還不會(huì)，這里附上隊(duì)列優(yōu)化迪杰斯特拉的解法

1 #include<iostream> 2 #include<cstdio> 3 #include<vector> 4 #include<string.h> 5 #include<queue> 6 #include<utility> 7 #define INF 0x3f3f3f3f 8 9 using namespace std; 10 typedef pair<int,int> P; 11 12 struct node 13 { 14 int to,w; 15 node(int v,int val):to(v),w(val) {} 16 }; 17 18 int n,m; 19 const int maxn = 100007; 20 int vis[maxn]; 21 int dist[maxn]; 22 vector<node>g[maxn]; 23 24 void init() 25 { 26 27 int a,b,c; 28 for(int i=0; i<=n; i++)g[i].clear(); 29 for(int i=0; i<m; i++) 30 { 31 scanf("%d%d%d",&a,&b,&c); 32 g[a].push_back(node(b,c)); 33 } 34 scanf("%d",&a); 35 for(int i=0; i<a; i++) 36 { 37 scanf("%d",&b); 38 g[0].push_back(node(b,0)); 39 } 40 scanf("%d",&a); 41 for(int i=0; i<a; i++) 42 { 43 scanf("%d",&b); 44 g[b].push_back(node(n+1,0)); 45 } 46 } 47 48 void dijkstra(int start) 49 { 50 priority_queue<P,vector<P>,greater<P> >que; 51 memset(dist,INF,sizeof(dist)); 52 dist[start] = 0; 53 que.push(P(0,start)); 54 while(!que.empty()) 55 { 56 P p = que.top(); 57 que.pop(); 58 int v = p.second; 59 if(dist[v]<p.first)continue; 60 for(int i=0; i<g[v].size(); i++) 61 { 62 node e = g[v][i]; 63 if(dist[e.to] > dist[v] + e.w) 64 { 65 dist[e.to] = dist[v] + e.w; 66 que.push(P(dist[e.to],e.to)); 67 } 68 } 69 } 70 } 71 72 int main() 73 { 74 while(~scanf("%d%d",&n,&m)) 75 { 76 init(); 77 dijkstra(0); 78 printf("%d\n",dist[n+1]); 79 } 80 return 0; 81 } View Code

?

轉(zhuǎn)載于:https://www.cnblogs.com/iwannabe/p/9132490.html

總結(jié)

以上是生活随笔為你收集整理的浪里个浪 FZU - 2261的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。