2013
12-13

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

GrassLand和他的实验室在1号路口，而他的师弟在n号路口。

GrassLand不希望走的太远而浪费科研的时间，所以他至多只会离开实验室k个路口。

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
****************************************************************/