题目1539:师弟
时间限制:1 秒
内存限制:128 兆
特殊判题:否
- 题目描述:
-
开学了,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
起点终点2次最短路,再枚举即可。#include <iostream> #include <stdio.h> #include <queue> using namespace std; const int size=1008 ; const int inf=100000000 ; struct Edge{ int v ; int w ; int next ; }edge[200008]; int id ; int vec[size] ; inline void add_edge(int u ,int v ,int w){ edge[id].v=v ; edge[id].w=w ; edge[id].next=vec[u] ; vec[u]=id++ ; } int dist[2][size] ,N ,M , K; bool in_queue[size] ,visited[size]; void spfa(int start){ int now=(start==1?0:1) ; for(int i=1;i<=N;i++){ dist[now][i]=inf ; in_queue[i]=0 ; } dist[now][start]=0 ; in_queue[start]=1 ; queue<int>que ; que.push(start) ; while(!que.empty()){ int u=que.front() ; que.pop() ; in_queue[u]=0 ; for(int e=vec[u];e!=-1;e=edge[e].next){ int v=edge[e].v ; int w=edge[e].w ; if(dist[now][v]>dist[now][u]+w){ dist[now][v]=dist[now][u]+w ; if(!in_queue[v]){ in_queue[v]=1 ; que.push(v) ; } } } } } struct Node{ int id ; int Len ; Node(){} ; Node(int i,int L):id(i),Len(L){} ; }; int bfs(){ //cout<<dist[0][N]<<" "<<dist[1][1]<<endl ; int ans=0 ; queue<Node>que ; fill(visited,visited+1+N,0) ; que.push(Node(1,0)) ; visited[1]=1 ; while(!que.empty()){ Node now=que.front() ; que.pop() ; int u=now.id ; if(now.Len>K) continue ; if(dist[0][u]+dist[1][u]==dist[0][N]) ans++ ; for(int e=vec[u];e!=-1;e=edge[e].next){ int v=edge[e].v ; if(!visited[v]){ que.push(Node(v,now.Len+1)) ; visited[v]=1 ; } } } return ans ; } int gao(){ id=0 ; fill(vec,vec+N+1 ,-1) ; int u ,v ,w ; for(int i=1;i<=M;i++){ scanf("%d%d%d",&u,&v,&w) ; add_edge(u,v,w) ; add_edge(v,u,w) ; } spfa(1) ; spfa(N) ; return bfs() ; } int main(){ while(scanf("%d%d%d",&N,&M,&K)!=EOF){ printf("%d ",gao()) ; } return 0 ; }