洛谷P1608 路径统计 最短路变种 dijkstra算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了洛谷P1608 路径统计 最短路变种 dijkstra算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1763字，纯文字阅读大概需要3分钟。
内容图文
题意：
求一个带权有向图的1到n的最短路径数量，两点间会有重边，两条最短路径只有在存在一条边及以上不同时认为不同（所以重边算一条边），若城市n无法到达则只输出一个(‘No answer’)。
题解：
和P1144差不多，但是P1144是无权图，所以可以直接bfs，本题是带权图，就需要使用dijkstra算法求最短路了，更新数量时，如果$dis[v]$需要松弛，则说明存在一条新的边缩短了$1$到$v$的最短距离，则最短路径数就是$dis[u]$，如果不需要松弛，就是$cnt[v]+=cnt[u]$，不存在$dis[v]<dis[u]$的情况。因为重边算一条边，所以在存图时需要去重，先用矩阵存，再转成邻接表或者直接使用矩阵存图跑dijkstra算法即可。
AC代码：
#include <iostream>
#include <queue>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
int dis[2005],vis[2005],cnt[2005];
struct edge
{
int to,w;
edge(int a,int b)
{
to=a,w=b;
}
bool operator<(const edge &a)const
{
return this->w>a.w;
}
};
vector<edge>node[2005];
void dijkstra(int n)
{
memset(dis,0x3f3f3f3f,sizeof(dis));
memset(vis,0,sizeof(vis));
memset(cnt,0,sizeof(cnt));
dis[1]=0,cnt[1]=1;
priority_queue<edge>que;
que.push(edge(1,dis[1]));
while(!que.empty())
{
edge u=que.top();
que.pop();
if(vis[u.to])
continue;
vis[u.to]=1;
for(int i=0;i<node[u.to].size();++i)
{
edge v=node[u.to][i];
if(!vis[v.to])
{
if(dis[v.to]==dis[u.to]+v.w)
cnt[v.to]+=cnt[u.to];
else if(dis[v.to]>dis[u.to]+v.w)
{
dis[v.to]=dis[u.to]+v.w;
cnt[v.to]=cnt[u.to];
que.push(edge(v.to,dis[v.to]));
}
}
}
}
/*for(int i=1;i<=n;++i)
cout<<dis[i]<<" ";
cout<<endl;*/
if(dis[n]>=0x3f3f3f3f)
cout<<"No answer"<<endl;
else
cout<<dis[n]<<" "<<cnt[n]<<endl;
}
int graph[2005][2005];
int main()
{
memset(graph,0x3f3f3f3f,sizeof(graph));
int n,m,a,b,c;
cin>>n>>m;
for(int i=0;i<m;++i)
{
cin>>a>>b>>c;
if(graph[a][b]>c)
graph[a][b]=c;
}
for(int i=1;i<=n;++i)
for(int j=1;j<=n;++j)
if(graph[i][j]<0x3f3f3f3f)
node[i].push_back(edge(j,graph[i][j]));
dijkstra(n);
return 0;
}
内容总结
以上是互联网集市为您收集整理的洛谷P1608 路径统计 最短路变种 dijkstra算法全部内容，希望文章能够帮你解决洛谷P1608 路径统计 最短路变种 dijkstra算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。