| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 3808 | Accepted: 1105 |
Description
In the year 2050, after different attempts of the UN to maintain peace in the world, the third world war broke out. The importance of industrial, commercial and military secrets obliges all the countries to use extremely sophisticated espionage services, so that each city in the world has at least one spy of each country. These spies need to communicate with other spies, informers as well as their headquarters during their actions. Unluckily there doesn’t exist a secure way for a spy to communicate during the war period, therefore the messages are always sent in code so that only the addressee is able to read the message and understand its meaning.
The spies use the only service that functions during the war period, the post. Each city has a postal agency where the letters are sent. The letters can be sent directly to their destination or to other postal agencies, until the letter arrives at the postal agency of the destination city, if possible.
The postal agency in city A can send a PRinted letter to the postal agency in city B if there is an agreement on sending letters, which determines the time, in hours, that a letter takes to reach city B from city A (and not necessarily the opposite). If there is no agreement between the agencies A and B, the agency A can try to send the letter to any agency so that the letter can reach its destination as early as possible
Some agencies are connected with electronic communication media, such as satellites and optical fibers. Before the war, these connections could reach all the agencies, making that a letter could be sent instantly. But during the period of hostilities every country starts to control electronic communication and an agency can only send a letter to another agency by electronic media (or instantly) if they are in the same country. Two agencies, A and B, are in the same country if a printed letter sent from any one of the agencies can be delivered to the other one.
The espionage service of your country has managed to obtain the content of all the agreements on sending messages existing in the world and desires to find out the minimum time to send a letter between different pairs of cities. Are you capable of helping them?
Input
The input contains several test cases. The first line of each test case contains two integer separated by a space, N (1 ≤ N ≤ 500) and E (0 ≤ E ≤ N2), indicating the numbers of cities (numbered from 1 to N) and of agreements on sending messages, respectively. Following them, then, E lines, each containing three integers separated by spaces, X, Y and H (1 ≤ X, Y ≤ N, 1 ≤ H ≤ 1000), indicating that there exist an agreement to send a printed letter from city X to city Y, and that such a letter will be delivered in H hours.
After that, there will be a line with an integer K (0 ≤ K ≤ 100), the number of queries. Finally, there will be K lines, each representing a query and containing two integers separated by a space, O and D (1 ≤ O, D ≤ N). You must determine the minimum time to send a letter from city O to city D.
The end of the input is indicated by N = 0.
Output
For each test case your program should produce K lines of output. The I-th line should contain an integer M, the minimum time, in hours, to send a letter in the I-th query. If there aren’t communication media between the cities of the query, you should print “Nao e possivel entregar a carta” (“It’s impossible to deliver the letter”).
Print a blank line after each test case.
Sample Input
4 51 2 52 1 103 4 84 3 72 3 651 21 31 44 34 13 31 2 102 3 13 2 131 33 13 20 0Sample Output
0660Nao e possivel entregar a carta10Nao e possivel entregar a carta0思路：Tarjan缩点后跑个最短路就行，刚好很久没写过最短路了，就三种写法都复习了一遍，最后提交情况如图：
Dijkstra + 堆优化 ： 219ms
spfa : 266ms
Floyd : 1000ms
代码：
Dijkstra + 堆优化：
#include <iostream>#include <cstdio>#include <cstdlib>#include<cstring>#include <string>#include <algorithm>#include <cmath>#include <cctype>#include<queue>#include<map>#include<stack>using namespace std;typedef long long ll;const int INF = 1e8;const int maxn = 550;struct Node{ int dis,id; friend bool Operator < (Node a,Node b){ return a.dis > b.dis; }}ans[maxn];struct P{ int u,v,w; int next;}G1[maxn*maxn],G2[maxn*maxn];int head_1[maxn],head_2[maxn];int vis[maxn],dfn[maxn],low[maxn],point[maxn];int n,m,num,cnt,tot;stack<int> S;priority_queue<Node> que;void init(void){ num = cnt = tot = 0; memset(head_1,-1,sizeof(head_1)); memset(head_2,-1,sizeof(head_2)); for(int i=0 ;i<=n ;i++){ vis[i] = dfn[i] = low[i] = point[i] = 0; }}void add_G1(int u,int v,int w){ G1[cnt].u = u; G1[cnt].v = v; G1[cnt].w = w; G1[cnt].next = head_1[u]; head_1[u] = cnt++;}void add_G2(int u,int v,int w){ G2[cnt].u = u; G2[cnt].v = v; G2[cnt].w = w; G2[cnt].next = head_2[u]; head_2[u] = cnt++;}void Tarjan(int x){ dfn[x] = low[x] = tot++; vis[x] = 1; S.push(x); for(int i=head_1[x] ; i != -1; i = G1[i].next){ int v = G1[i].v; if(!dfn[v]){ Tarjan(v); low[x] = min(low[x],low[v]); } else if(vis[v]){ low[x] = min(low[x],dfn[v]); } } if(dfn[x] == low[x]){ num++; while(1){ int tem = S.top(); S.pop(); vis[tem] = 0; point[tem] = num; if(tem == x) break; } }}void Dijkstra(int s){ while(que.size()) que.pop(); memset(vis,0,sizeof(vis)); for(int i=1 ;i<=num ;i++){ ans[i].dis = INF; ans[i].id = i; } ans[s].dis = 0; que.push(ans[s]); while(que.size()){ Node u = que.top(); que.pop(); if(vis[u.id]) continue; vis[u.id] = 1; for(int i=head_2[u.id] ;i!=-1 ;i = G2[i].next){ int v = G2[i].v; if(u.dis + G2[i].w < ans[v].dis && (!vis[v])){ ans[v].dis = u.dis + G2[i].w; que.push(ans[v]); } } }}int main(){ while(scanf("%d%d",&n,&m) != EOF && n){ init(); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add_G1(u,v,w); } for(int i=1 ;i<=n ;i++){ if(!dfn[i]) Tarjan(i); } cnt = 0; for(int i=1 ;i<=n ;i++){ for(int j=head_1[i] ;j != -1 ;j = G1[j].next){ int v = G1[j].v; if(point[v] != point[i]){ add_G2(point[i],point[v],G1[j].w); } } } int Q; scanf("%d",&Q); while(Q--){ int u,v; scanf("%d%d",&u,&v); Dijkstra(point[u]); int w = ans[point[v]].dis; if(w == INF) printf("Nao e possivel entregar a carta/n"); else printf("%d/n",w); } printf("/n"); } return 0;}Floyd：
#include <iostream>#include <cstdio>#include <cstdlib>#include<cstring>#include <string>#include <algorithm>#include <cmath>#include <cctype>#include<queue>#include<map>#include<stack>using namespace std;typedef long long ll;const int INF = 1e8;const int maxn = 550;struct P{ int u,v,w; int next;}G1[maxn*maxn];int G2[maxn][maxn];int head_1[maxn],head_2[maxn];int vis[maxn],dfn[maxn],low[maxn],dis[maxn],point[maxn];int n,m,num,cnt,tot;stack<int> S;queue<int> que;void init(void){ num = cnt = tot = 0; memset(head_1,-1,sizeof(head_1)); memset(head_2,-1,sizeof(head_2)); for(int i=0 ;i<=n ;i++){ vis[i] = dfn[i] = low[i] = point[i] = 0; }}void add_G1(int u,int v,int w){ G1[cnt].u = u; G1[cnt].v = v; G1[cnt].w = w; G1[cnt].next = head_1[u]; head_1[u] = cnt++;}void Tarjan(int x){ dfn[x] = low[x] = tot++; vis[x] = 1; S.push(x); for(int i=head_1[x] ; i != -1; i = G1[i].next){ int v = G1[i].v; if(!dfn[v]){ Tarjan(v); low[x] = min(low[x],low[v]); } else if(vis[v]){ low[x] = min(low[x],dfn[v]); } } if(dfn[x] == low[x]){ num++; while(1){ int tem = S.top(); S.pop(); vis[tem] = 0; point[tem] = num; if(tem == x) break; } }}void Floyd(void){ for(int k=1 ;k<=num ;k++){ for(int i=1 ;i<=num ;i++){ for(int j=1 ;j<=num ;j++){ if(G2[i][k] + G2[k][j] < G2[i][j]) G2[i][j] = G2[i][k] + G2[k][j]; } } }}int main(){ while(scanf("%d%d",&n,&m) != EOF && n){ init(); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add_G1(u,v,w); } for(int i=1 ;i<=n ;i++){ if(!dfn[i]) Tarjan(i); } cnt = 0; for(int i=1 ;i<=num ;i++){ for(int j=1 ;j<=num ;j++){ if(i == j) G2[i][j] = 0; else G2[i][j] = INF; } } for(int i=1 ;i<=n ;i++){ for(int j=head_1[i] ;j != -1 ;j = G1[j].next){ int v = G1[j].v; if(point[v] != point[i]){ G2[point[i]][point[v]] = min(G2[point[i]][point[v]],G1[j].w); } } } Floyd(); int Q; scanf("%d",&Q); while(Q--){ int u,v; scanf("%d%d",&u,&v); int w = G2[point[u]][point[v]]; if(w == INF) printf("Nao e possivel entregar a carta/n"); else printf("%d/n",w); } printf("/n"); } return 0;}Spfa：
#include <iostream>#include <cstdio>#include <cstdlib>#include<cstring>#include <string>#include <algorithm>#include <cmath>#include <cctype>#include<queue>#include<map>#include<stack>using namespace std;typedef long long ll;const int INF = 0x3f3f3f3f;const int maxn = 550;struct P{ int u,v,w; int next;}G1[maxn*maxn],G2[maxn*maxn];int head_1[maxn],head_2[maxn];int vis[maxn],dfn[maxn],low[maxn],dis[maxn],point[maxn];int n,m,num,cnt,tot;stack<int> S;queue<int> que;void init(void){ num = cnt = tot = 0; memset(head_1,-1,sizeof(head_1)); memset(head_2,-1,sizeof(head_2)); for(int i=0 ;i<=n ;i++){ vis[i] = dfn[i] = low[i] = point[i] = 0; }}void add_G1(int u,int v,int w){ G1[cnt].u = u; G1[cnt].v = v; G1[cnt].w = w; G1[cnt].next = head_1[u]; head_1[u] = cnt++;}void add_G2(int u,int v,int w){ G2[cnt].u = u; G2[cnt].v = v; G2[cnt].w = w; G2[cnt].next = head_2[u]; head_2[u] = cnt++;}void Tarjan(int x){ dfn[x] = low[x] = tot++; vis[x] = 1; S.push(x); for(int i=head_1[x] ; i != -1; i = G1[i].next){ int v = G1[i].v; if(!dfn[v]){ Tarjan(v); low[x] = min(low[x],low[v]); } else if(vis[v]){ low[x] = min(low[x],dfn[v]); } } if(dfn[x] == low[x]){ num++; while(1){ int tem = S.top(); S.pop(); vis[tem] = 0; point[tem] = num; if(tem == x) break; } }}int spfa(int u,int v){ memset(vis,0,sizeof(vis)); memset(dis,INF,sizeof(vis)); while(que.size()) que.pop(); dis[u] = 0; vis[u] = 1; que.push(u); while(que.size()){ int tem = que.front(); que.pop(); vis[tem] = 0; for(int i = head_2[tem] ;i != -1 ;i = G2[i].next){ int p = G2[i].v; if(dis[p] > dis[tem] + G2[i].w){ dis[p] = dis[tem] + G2[i].w; if(!vis[p]){ vis[p] = 1; que.push(p); } } } } return dis[v];}int main(){ while(scanf("%d%d",&n,&m) != EOF && n){ init(); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); add_G1(u,v,w); } for(int i=1 ;i<=n ;i++){ if(!dfn[i]) Tarjan(i); } cnt = 0; for(int i=1 ;i<=n ;i++){ for(int j=head_1[i] ;j != -1 ;j = G1[j].next){ int v = G1[j].v; if(point[v] != point[i]){ add_G2(point[i],point[v],G1[j].w); } } } int Q; scanf("%d",&Q); while(Q--){ int u,v; scanf("%d%d",&u,&v); int w = spfa(point[u],point[v]); if(w == INF) printf("Nao e possivel entregar a carta/n"); else printf("%d/n",w); } printf("/n"); } return 0;}
新闻热点
疑难解答
