软件世界网 购物 网址 三丰软件 | 小说 美女秀 图库大全 游戏 笑话 | 下载 开发知识库 新闻 开发 图片素材
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
移动开发 架构设计 编程语言 Web前端 互联网
开发杂谈 系统运维 研发管理 数据库 云计算 Android开发资料
  软件世界网 -> 开发杂谈 -> 【POJ3114】CountriesinWar(Tarjan+Dijkstra) -> 正文阅读
开发杂谈 最新文章
BloomFilter
大学四年编程之历程
内核分析
造人论坛——意识的本质和一个人工脑模型
OFDM信号[matlab描述]
人类还会进化吗?
HDUACM1035RobotMotion简单模拟题
树、二叉树(二)
iisphpweb.config处理404,500等,跳转友好
DatabaseAsaFortress

[开发杂谈]【POJ3114】CountriesinWar(Tarjan+Dijkstra)

  2016-03-09 15:31:52

【POJ 3114】Countries in War(Tarjan+Dijkstra)
Countries in War
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 3240   Accepted: 945

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 ≤ EN2), 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, YN, 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, DN). 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 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

Sample Output
0
6
6
0
Nao e possivel entregar a carta

10
Nao e possivel entregar a carta
0

Source
South America 2006, Brazil Subregion
题目大意:有n个村庄,e条路把某些村庄两两相连,如果某几个点可以互相访问到,或者说构成强联通子图,这几个点就算为一个城市。
城市内部的点互相访问不需要开销,给出k次询问,每次询问a到b的最短路径
强联通缩点然后缩点重新构图,对于每次询问跑最短路,Floyd会爆炸。手残把tarjan的访问标记开成了bool 找了半天错……
代码如下:
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <queue>
#include <stack>
#include <list>
#include <algorithm>
#include <map>
#include <set>
#define LL long long
#define Pr pair<int,int>
#define fread() freopen("data.in","r",stdin)
#define fwrite() freopen("my.out","w",stdout)

using namespace std;
const int INF = 0x3f3f3f3f;
const int msz = 10000;
const int mod = 1e9+7;
const double eps = 1e-8;

struct Edge
{
	int v,w,next;
};

int head[555];
int mp[555][555];
Edge eg[255555];

int vis[555];
int dfn[555],low[555];
int dis[555];
int to[555];
int n,e,tim,tp;
stack <int> s;

void tarjan(int u)
{
	vis[u] = 1;
	s.push(u);
	dfn[u] = low[u] = tim++;
	int v;

	for(int i = head[u]; ~i; i = eg[i].next)
	{
		v = eg[i].v;
		if(!vis[v])
		{
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}else if(vis[v] == 1) low[u] = min(low[u],dfn[v]);
	}

	if(dfn[u] == low[u])
	{
		v = s.top();
		to[v] = tp;
		vis[v] = -1;
		s.pop();

		while(v != u)
		{
			v = s.top();
			to[v] = tp;
			vis[v] = -1;
			s.pop();
		}

		tp++;
	}
}

int Dijkstra(int st,int en)
{
	memset(dis,INF,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[st] = 0;

	int p,m;

	while(1)
	{
		m = INF;
		p = -1;
		for(int i = 0; i < tp; ++i)
			if(!vis[i] && dis[i] < m)
			{
				m = dis[i];
				p = i;
			}

		if(p == en) return dis[p];
		if(p == -1) return INF;
		vis[p] = 1;

		for(int i = 0; i < tp; ++i)
			if(!vis[i] && dis[i] > dis[p]+mp[p][i])
				dis[i] = dis[p]+mp[p][i];
	}

}

int main()
{
//	fread();
//	fwrite();

	int u,v,w;

	while(~scanf("%d%d",&n,&e) && n)
	{
		memset(head,-1,sizeof(head));

		for(int i = 0; i < e; ++i)
		{
			scanf("%d%d%d",&u,&v,&w);
			eg[i].v = v;
			eg[i].w = w;
			eg[i].next = head[u];
			head[u] = i;
		}

		memset(vis,0,sizeof(vis));
		tim = tp = 0;
		for(int i = 1; i <= n; ++i)
			if(!vis[i]) tarjan(i);

		memset(mp,INF,sizeof(mp));
		for(int i = 1; i <= n; ++i)
			for(int j = head[i]; ~j; j = eg[j].next)
				mp[to[i]][to[eg[j].v]] = min(mp[to[i]][to[eg[j].v]],eg[j].w);

		for(int i = 0; i < tp; ++i) mp[i][i] = 0;

		scanf("%d",&e);
		while(e--)
		{
			scanf("%d%d",&u,&v);
			int tmp = Dijkstra(to[u],to[v]);
			if(tmp == INF) puts("Nao e possivel entregar a carta");
			else printf("%d\n",tmp);
		}
		puts("");
	}

	return 0;
}



上一篇文章      下一篇文章      查看所有文章
2016-03-09 15:31:34  
360图书馆 论文大全 母婴/育儿 软件开发资料 网页快照 文字转语音 购物精选 软件 美食菜谱 新闻中心 电影下载 小游戏 Chinese Culture
生肖星座解梦 三沣玩客 拍拍 视频 开发 Android开发 站长 古典小说 网文精选 搜图网 天下美图 中国文化英文 多播视频 装修知识库
2017-1-19 0:02:40
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  软件世界网 --