[URI ONLINE JUDGE] – 1148 – Countries at War

In year 2050, after several attempting of ONU to maintain the peace in world, exploded the third world war. Industrial secrets, commercials and military forced all countries to utilize extremely sophisticated espionage services, in order to have one spy of each country in each city in the world. These spies need to communicate with others spies, informants and even with both centrals during their actions. Unfortunately, there’s no safe way for a spy to communicate within a war building, therefore the messages are always sent in code so that only the receiver is able to read and understand it.

The spies use the only service available in war time, the post offices. Each city has one post office where letters can be sent. Letters can be sent directly to its destination or to other post offices, until it arrives to the post office of the intended city, if possible.

A post office in city A can send a printed letter directly to a post office in city B if there’s a letter sending agreement, which determines the time, measured in hours, that a letter takes to travel from city A to cityB (and not necessarily the opposite). If there’s no agreement between the cities, then post office A can try to send the letter to as many other post offices as necessary, until it is delivered to its destination, if possible.
Some post offices are electronically interconnected with satellites and optical fiber. Before war, these connections could reach all offices, making a letter to be sent instantly, but during hostilities period, each country began to control the electronic communication, and one office can only send a letter electronically to other, if both offices are in the same country. Two post offices, A and B, are in the same country if there’s any way that a printed letter sent from one office is delivered in the other one.
The espionage service of your country was able to obtain all letter sending agreements in the world e wishes to find out the minimum time for sending a letter between various pairs of cities. Would you be able to help it?

Input

The input contains several test cases. The first line of each case contains two integers separated by a White space, N (1 ≤ N ≤ 500) and E (0 ≤ EN2), indicating the number of cities (enumerated from 1 to N) and of letter sending agreements, respectively. Follow, then, E lines, each one with three integers separated by a White space, X, Y and H (1 ≤ X, YN, 1 ≤ H ≤ 1000), indicating that there is an agreement to sending a printed letter from city X to city Y, and that this letter will be delivered in H hours.

Next, there will be a line with an integer K (0 ≤ K ≤ 100), the number of queries. Finally, K lines of input, each one representing a query that contains two integers separated by a white space, O and D (1 ≤ O, DN). You should determine the minimum time for sending a letter from city O to city D. The end of input is determined by N = E = 0.

Output

For each test case, your program must output K lines. The N-th line should contain an integer M, the minimum time in hours, for sending a letter in the N-th query. If there’s no communication way between the cities of the query, you should print: “Nao e possivel entregar a carta” ( ‘The letter could not be delivered’ in portuguese).

Print a blank line after each case.

Sample Input Sample Output
4 5
1 2 5
2 1 10
3 4 8
4 3 7
2 3 6
5
1 2
1 3
1 4
4 3
4 1
3 3
1 2 10
2 3 1
3 2 1
3
1 3
3 1
3 2
0 0
0
6
6
0
Nao e possivel entregar a carta

10
Nao e possivel entregar a carta
0

 

 

solution:

 

#include <iostream>
#include "stdio.h"
#include <string.h>
#define INF 0x3F3F3F3F
#define MAX 501
using namespace std;

int g[510][510];
int dist[510];
bool visit[510];
int pred[MAX];

void dijkstra(int ordem, int s){
int p[ordem];
int t = -1;
int v;

for (int i = 0; i <= ordem; i++)
dist[i] = INF;

dist[s] = 0;
p[++t] = s;

while(t != -1){
v = p[t--];
for (int i = 1; i <= ordem; i++){
if(dist[i] > dist[v] + g[v][i]){
dist[i] = dist[v] + g[v][i];
p[++t] = i;
}
}
}
}

void dijkstra2 (int n,int p){
int v,c;

memset (dist, INF, sizeof(dist));
memset (visit, 0, sizeof(visit));
memset (pred, -1, sizeof(pred));

dist[p] = 0;
v = p;

while (!visit[v]){
visit[v] = true;
for (int i=1; i<=n; i++){
if (g[v][i] != INF){
c = g[v][i];
if (dist[i] > dist[v]+c){
dist[i] = dist[v]+c;
pred[i] = v;
}
}
}
v = 0;
c = INF;
for (int i=1; i<=n; i++){
if(visit[i] == false && c>dist[i]){
c=dist[i];
v=i;
}
}
}
}

int main(){

long long int aux;
int n,e,x,y,h,k,o,d;

while(1){

cin >> n >> e;

if(n == 0 && e == 0) break;

for (int i = 0; i <= n; i++)
for (int j = 0; j <= n; j++)
g[i][j] = INF;

while(e--){
cin >> x >> y >> h;
g[x][y] = h;
}

for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if(g[i][j] != INF && g[j][i] != INF){
g[i][j] = 0;
g[j][i] = 0;
}
}
}

cin >> k;

while(k--){
cin >> o >> d;
dijkstra2(n,o);

if(dist[d] < INF)
cout << dist[d] << endl;
else
cout << "Nao e possivel entregar a carta" << endl;
}

cout << endl;
}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s