最短路计数 路径统计

题意：给出一个有向图，有重边，求从 1 1 号点到nn号点的最短路长度和数量。

去年NOIP的时候连这个都不会，D1T3 30分暴力都没拿到，我还是太弱了。

最短路长度跑堆优化 dij d i j 就行，而最短路的数量也可以在跑 dij d i j 的时候计算出，有以下两种情况：

1.如果搜索到的点 v v 到起点的距离(dis[v])(dis[v])等于当前点 x x 到起点的距离(dis[x])(dis[x])加上这两点间的那条边的距离 (e[i].dis) ( e [ i ] . d i s ) ，那么我们就将搜索到的点 v v 的最短路径数加上当前点uu的最短路径数，即：

if(dis[v]==dis[x]+e[i].dis)
ans[v]+=ans[x];

2.如果我们更新了搜索到的点 v v 到起点的最短距离，那么我们将到达搜索到的点vv的最短路径数改为当前点 x x <script type="math/tex" id="MathJax-Element-14">x</script>的最短路径数，即：

if(dis[v]>dis[x]+e[i].dis)
{
dis[v]=dis[x]+e[i].dis;
ans[v]=ans[x];
q.push(make_pair(-dis[v],v));
}

注意去重边

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
int next,dis,to;
}e[1001000];
priority_queue <pair<int,int> > q;
int head[1001000],dis[1001000],num,n,m;
int ans[1001000],u,v,d,g[2500][2500];
bool book[1001000];
inline void add(int from,int to,int dis)
{
e[++num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num;
}
inline void dij(int start)
{
for(register int i=1;i<=n;++i)
dis[i]=2000000000;
dis[start]=0;
ans[start]=1;
q.push(make_pair(0,start));
while(!q.empty())
{
int x=q.top().second;
q.pop();
if(book[x])
continue;
book[x]=1;
for(register int i=head[x];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]>dis[x]+e[i].dis)
{
dis[v]=dis[x]+e[i].dis;
ans[v]=ans[x];
q.push(make_pair(-dis[v],v));
}
else if(dis[v]==dis[x]+e[i].dis)
ans[v]+=ans[x];
}
}
}
inline int read()
{
register int x=0;
register char s=getchar();
while(s>'9'||s<'0')
s=getchar();
while(s<='9'&&s>='0')
{
x=(x<<3)+(x<<1)+s-'0';
s=getchar();
}
return x;
}
int main()
{
cin>>n>>m;
for(register int i=1;i<=n;++i)
for(register int j=1;j<=n;++j)
g[i][j]=999999999;
for(register int i=1;i<=m;++i)
{
u=read();
v=read();
d=read();
if(g[u][v]<=d)//去重边
continue;
g[u][v]=d;
add(u,v,d);
}
dij(1);
if(dis[n]==2000000000)
cout<<"No answer";
else
cout<<dis[n]<<" "<<ans[n];
} 

最后

以上就是聪慧薯片为你收集整理的最短路计数 路径统计的全部内容，希望文章能够帮你解决最短路计数 路径统计所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。