P1608 路径统计（最短路数统计）

· · 个人记录

P1608 路径统计

这一道题是P1144的加强版，我们先来看看P1144是如何求解的： 题目要求的是求出每个顶点所对应的最短路径的条数，而这道题中边的权值都为1，所以和最短路联系起来的话不难想到可以用BFS。 但是毕竟我刚学了最短路系列算法怎么可能不用呢，所以在P1144中采用了Dijkstra算法 其实完全没必要，实现了后发现和BFS没啥区别 主要思想： 到第i个顶点的最短路径是第i个顶点的所有前趋顶点（就是从起点到i的最短路径上i的前一个顶点）最短路径条数之和（有点动态规划的赶脚了） 由于Dijkstra是按每个顶点最短路径的长度从小到大遍历，所以保证了求第i个顶点的最短路径的时候它的前趋顶点的最短路径都被求出了（实际上是动态规划的思想，无后效性），而且又因为每条边只会被遍历一次，所以可以想到用Dijkstra算法在遍历边的时候做一些手脚，就可以求出第i个顶点的最短路条数：

利用数组来记录每个顶点的最短路条数，遍历边时，如果下一顶点对应的花费d[a]和当前路径的花费d[v]+1相同那么就加上当前顶点的
最短路条数，如果比当前路径大，那么说明下一顶点之前的路径并非是最短路径，这时我们就需要更新顶点值和它对应的最短路径条数

这一部分的代码：

for(int i=0;i<g[v].size();i++)  //边的遍历，v是当前所取的顶点
        {
            int &a=g[v][i]; //下一个顶点
            if(d[v]+1<d[a]) //如果小于则更新
            {
                d[a]=d[v]+1;
                que.push(P(d[a],a));        //最普通的dijkstra
                ways[a]=ways[v];//路径长度重置，路径条数也要重置
            }
            else
            if(d[v]+1==d[a])ways[a]+=ways[v];//当前路径与之相等则加上
            ways[a]%=MOD;//每次都mod一下以免爆掉
        }

完整代码：

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<utility>
using namespace std;
const int MAX_N=1e6+1;
const int MOD=100003;
typedef pair<int,int> P;
int d[MAX_N],ways[MAX_N];       //ways数组记录最短路条数
inline int read()
{
    int sum=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+c-48;c=getchar();}
    return sum*f;
}
int main()
{
    int n,m;
    n=read(),m=read();
    int from,to;
    vector<int> g[n+1];
    for(int i=0;i<m;i++)
    {
        from=read(),to=read();
        if(from==to)continue;       //自环没有影响，直接去掉
        g[from].push_back(to);
        g[to].push_back(from);
    }
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,1));
    fill(d,d+n+1,MAX_N);//dijkstra算法准备工作得做好
    d[1]=0;
    ways[1]=1;          //记得把第一个顶点的最短路数设为1
    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int value=p.first,v=p.second;
        if(value>d[v])continue;
        for(int i=0;i<g[v].size();i++)
        {
            int &a=g[v][i];
            if(d[v]+1<d[a])
            {
                d[a]=d[v]+1;
                que.push(P(d[a],a));
                ways[a]=ways[v];        
            }
            else
            if(d[v]+1==d[a])ways[a]+=ways[v];
            ways[a]%=MOD;
        }
    } 
    for(int i=1;i<=n;i++)printf("%d\n",ways[i]%MOD);
    return 0;
}

再来看P1608路径统计，实际上和这个一样就是边的权值不是1了，我们只需要把权值加入进去就行了，另外本题主要是数据有点儿坑，要手动排除重复边（权值相同），还有就是会有重边（权值不同），但是因为是最短路问题，所以只需要取所有重边中权值最小的就行 完整代码：

#include<iostream>
#include<queue>
#include<vector>
#include<cstdio>
#include<utility>
using namespace std;
const int MAX_N=2e3+1;
typedef pair<int,int> P;
int d[MAX_N],ways[MAX_N];
char dist[MAX_N][MAX_N];
inline int read()
{
    int sum=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){sum=(sum<<1)+(sum<<3)+c-48;c=getchar();}
    return sum*f;
}
int main()
{
    int n,m;
    n=read(),m=read();
    int from,to,cost;
    vector<P> g[n+1];
    for(int i=0;i<m;i++)
    {
        from=read(),to=read(),cost=read();
        if(dist[from][to]>cost||!dist[from][to])
        {
            g[from].push_back(P(to,cost));
            dist[from][to]=cost;
        }
    }
    priority_queue<P,vector<P>, greater<P> > que;
    que.push(P(0,1));
    fill(d,d+n+1,(int)1e9);
    d[1]=0;
    ways[1]=1;
    while(!que.empty())
    {
        P p=que.top();
        que.pop();
        int value=p.first,v=p.second;
        if(value>d[v])continue;
        for(int i=0;i<g[v].size();i++)
        {
            P k=g[v][i];
            cost=k.second;
            int a=k.first;
            if(d[v]+cost<d[a])      //同P1144只是权值不是固定的1
            {
                d[a]=d[v]+cost;
                que.push(P(d[a],a));
                ways[a]=ways[v];
            }
            else
            if(d[v]+cost==d[a])ways[a]+=ways[v];
        }
    }
    if(ways[n])
    {
        cout<<d[n]<<" "<<ways[n];
    }
    else cout<<"No answer";
    return 0;
}