P1608 路径统计-题解

· · 题解

大家好，这里是蒟蒻天鹏。

主体思路：裸Dijkstra+矩阵存图 为什么不用SPFA？众所周知，它死了。
相信各位对于最短路早已是轻车熟路，故不过多赘述。而题目中还要求输出最短路径的条数，怎么办呢？

我们假设这样一个图的存在：

在这个图中，由A-D的最短路径共有三条，分别是A-D,A-B-D,A-B-C-D，长度都是30
接下来我们再对这个图搞事情：

可以看到，由A-E的最短路径还是三条，长度是40。
这个时候我们发现了一个好玩的特性，A-E的条数就是A-D的条数！别着急，我们再稍加修改：

现在A-F的条数是1条，距离为10，加入F-E的距离(30)后，距离为40；A-D的条数是3条，距离为30，加入D-E的距离(10)后，距离为40；A-E的条数是4条。可以发现，由于40=40,A-E的条数就是A-F,A-D的条数之和。我们再去做做修改：

此时，A-G的最短路径条数是1条，加上关联边长度为20；A-F,A-D的最短路径条数分别是1条和3条，加上关联边长度为40；由于40=40>20，所以A-E的最短路径条数是1条，距离为20。于是我们可以归纳一下：

求节点n的最短距离条数，先要求其节点关联节点的最短路径距离+关联边的长度，之后选出最短的，将它们的最短距离条数加和。（好麻烦啊）

这是个好东西，怎么用呢？

众所周知，dijsktra在求最短路的时候会更新距离，我们可以新建一个path数组存路径条数，在更新距离的时候可以直接对距离更新。核心代码:

//dijisktra更新距离时：
if(dis[j]>dis[u]+w)
{
    dis[j]=dis[u]+w;
    path[j]=path[u];//不同长度变最短
}
else if(dis[j]==dis[u]+w)
    path[j]+=path[u];//相同长度加和

轻松愉悦

下面是完整的代码：

#include <bits/stdc++.h>
using namespace std;
int tu[2010][2010];//不要在意这个细节
bool vis[2010]={0};
int dis[2010],path[2010];
int n,m,from,I,J,C;
void dij(int a）//常规的dij
{
    memset(dis,0x3f,sizeof(dis));
    dis[a]=0;
    for(int i=1;i<=n;i++)
    {
        int u,maxu=1e9;
        for(int j=1;j<=n;j++)
            if(!vis[j]&&maxu>dis[j])
            {
                maxu=dis[j];
                u=j;
            }
        vis[u]=1;
        for(int j=1;j<=n;j++)
        {
            int w=tu[u][j];
            if(dis[j]>dis[u]+w)
            {
                dis[j]=dis[u]+w;
                path[j]=path[u];//不同长度变最短
            }
            else if(dis[j]==dis[u]+w)
                path[j]+=path[u];//相同长度加和
        }
    }
}
int main()
{   
    memset(tu,63,sizeof(tu));
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>I>>J>>C;
        if(tu[I][J]>C)
        {
            tu[I][J]=C; //注意有向图 
        }
    }

    dij(1);
    if(dis[n]==0x3f3f3f3f)//如果还是初值，输出no ans
        cout<<"No answer"<<endl;
    else
        cout<<dis[n]<<" "<<path[n];
    return 0;
}