首页 > ACM题库 > 九度OJ > 九度-1539-师弟[解题代码]
2013
12-13

九度-1539-师弟[解题代码]

题目描述:

开学了,GrassLand的新师弟也来了,于是GrassLand打算去路口接他,以表兄长之谊。
已知:
共有n个路口,n个路口间存在着m条道路,每条道路连接两个路口,道路有其各自的长度。
GrassLand和他的实验室在1号路口,而他的师弟在n号路口。
师弟沿着最短路径走向实验室,若有多于一条的最短路径,他会任意选择一条。
GrassLand不希望走的太远而浪费科研的时间,所以他至多只会离开实验室k个路口。
问题出现了,GrassLand并不知道他的师弟会选择哪条路径。所以他想知道,所有离开实验室不超过k个路口(即该路口和实验室可以由至多k条道路连接)的路口中,在师弟和实验室间任意一条最短路径上的路口个数(包括实验室所在的1号路口和师弟所在的n号路口)。

输入:

输入包含多组测试用例。
每组测试用例开头为三个整数n(2 <= n <= 1000),m(1 <= m <= 100000),k(0 <= k <= 1000)
接下去m行描述道路信息,每行三个整数a(1 <= a <= n),b(1 <= b <= n && b != a),c(1 <= c <= 1000),表示连接路口a和路口b的道路长度为c。
数据保证1号路口和n号路口间连通。

输出:

对于每组测试用例,输出一个整数,代表符合条件的路口个数。

样例输入:
4 3 2
1 2 1
2 3 1
3 4 1
4 3 1
1 2 1
2 3 1
3 4 1
4 4 1
1 2 3
1 3 2
2 4 2
3 4 3
样例输出:
3
2
3

cpp 代码如下:
#include <iostream>
#include <queue>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;
const int N = 1001;

class Node
{
public:
	int e, cost;
	Node(int n, int c)
	{
		e = n;
		cost = c;
	}

};
int n, m, k;
vector<Node> edges[N];
vector<Node>::iterator iter1;
vector<int>::iterator iter2;
bool canVisit[N];

//得到限制范围内的那些点,存储在canVisit中
void getK()
{
	queue<Node> q;
	Node start(1, 0);
	q.push(start);
	canVisit[1] = true;
	while (q.size() > 0)
	{
		Node n = q.front();
		q.pop();
		if (n.cost >= k)
			break;
		for (iter1 = edges[n.e].begin(); iter1 != edges[n.e].end(); iter1++)
		{
			if (!canVisit[iter1->e])
			{
				canVisit[iter1->e] = true;
				Node newNode(iter1->e, n.cost + 1);
				q.push(newNode);
			}
		}
	}
	//for (int i = 0; i <= n; i++)
	//	cout << canVisit[i] << ",";
	//cout << endl;
}

int dis1[N]; //正向
int dis2[N]; //逆向

//计算从点start到其他所有节点的最短距离
void bfs(int start, int * dis)
{
	queue<int> q;
	q.push(start);
	bool visit[N] ={ false };
	dis[start]=0;
	while (q.size() > 0)
	{
		int e = q.front();
		q.pop();
		visit[e] = false;
		for (iter1 = edges[e].begin(); iter1 != edges[e].end(); iter1++)
		{
			//-1表示第一次到到改点
			if (dis[iter1->e] == -1 || dis[iter1->e] > dis[e] + iter1->cost)
			{
				dis[iter1->e] = dis[e] + iter1->cost;
				if (!visit[iter1->e])
				{
					q.push(iter1->e);
					visit[iter1->e] = false;
				}
			}
		}
	}
	  // for(int i=0; i<=n; i++) cout << dis[i] << ",";
	 //       cout << endl;
}

void dij(int start, int * dis){
	int cnt = 0;
	bool visit[N] = {false};
	for(iter1=edges[start].begin(); iter1!=edges[start].end(); iter1++){
		dis[iter1->e] = iter1->cost;
	}
dis[start]=0;
	visit[start] = true;
	int M = 1000000000;
//	while(true){
	for(int i=1; i<n; i++){
		int index = 0, mint = M;
		for(int j=1; j<=n; j++){
			if(!visit[j] && dis[j]!=-1 && dis[j] < mint){
				mint = dis[j];
				//path[j] = start;
				//cout << j << " " << start << endl;
				index = j;
			}
		}

		visit[index] = true;
			//到达终点
		start = index;
		for(iter1=edges[start].begin(); iter1!=edges[start].end(); iter1++){
			if(!visit[iter1->e]  && (dis[iter1->e] > dis[start]+iter1->cost || dis[iter1->e]==-1))
				dis[iter1->e] = dis[start]+iter1->cost;
		}


	}
	//cout << "dij: ";
	//for(int i=0; i<=n; i++) cout << dis[i] << ",";
	//	        cout << endl;
}


int main()
{
	int a,b,c;

	while (scanf ("%d%d%d",&n,&m,&k) != EOF)
	{
		memset(edges, 0, sizeof(edges));
		memset(canVisit, 0 ,sizeof(canVisit));
		memset(dis1, -1, sizeof(dis1));
		memset(dis2, -1, sizeof(dis2));
		for(int i=0; i<m; i++)
		{
			scanf("%d%d%d",&a,&b,&c);
			edges[a].push_back(Node(b,c));
			edges[b].push_back(Node(a,c));
		}
		getK();
		bfs(1,dis1);
		bfs(n,dis2);
		//dij(1,dis1);
		//dij(n,dis2);
		int ans=0;
		//统计最总结果
		for(int i=1; i<=n; i++){
			if(canVisit[i] && dis1[i] != -1 && dis2[i]!= -1){
				if(dis1[i] + dis2[i] == dis1[n])
					ans++;
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}
/**************************************************************
	Problem: 1539
	User: coder
	Language: C++
	Result: Accepted
	Time:500 ms
	Memory:12252 kb
****************************************************************/