题目描述
求从S到F的最短路径和最短路径加一的数量
算法
先用dijkstra遍历出每个点离终点F的最短距离,在用dfs计算路径数量
时间复杂度
$O(T*mlog(n))$
参考文献
C++ 代码
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=1010,M=20010;
int T;
int n,m,s,t;
int h[M],e[M],rh[M],w[M],ne[M],idx;
int dist[N],res;
int cnt[N];
bool st[N];
void add(int a,int b,int c,int h[]){
e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++;
}
void dijkstra(){
memset(dist,0x3f,sizeof dist);
dist[t]=0;
memset(st,0,sizeof st);
priority_queue<PII,vector<PII>,greater<PII>>heap;
heap.push({dist[t],t});
while(heap.size()){
PII t=heap.top();
heap.pop();
int ver=t.y;
if(st[ver])continue;
st[ver]=true;
for(int i=rh[ver];~i;i=ne[i]){
int j=e[i];
if(dist[j]>dist[ver]+w[i]){
dist[j]=dist[ver]+w[i];
heap.push({dist[j],j});
}
}
}
}
void dfs(int u,int dis){
if(st[u])return;
st[u]=true;
for(int i=h[u];~i;i=ne[i]){
int j=e[i],len=dis+w[i]+dist[j];
if(len<=res+1){
dfs(j,dis+w[i]);
cnt[u]+=cnt[j];
}
}
}
int main(){
cin>>T;
while(T--){
memset(h,-1,sizeof h);
memset(rh,-1,sizeof rh);
idx=0;
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b,c;
cin>>a>>b>>c;
add(a,b,c,h),add(b,a,c,rh);
}
cin>>s>>t;
dijkstra();
memset(cnt,0,sizeof cnt);
memset(st,0,sizeof st);
res=dist[s],cnt[t]=1;
dfs(s,0);
cout<<cnt[s]<<endl;
}
return 0;
}