P1608 路径统计

· · 题解

P1608 路径统计 题解

不喜欢 dijkstra 优化的同学可以看过来。

前置知识 ： dijkstra 以及其性质的足够了解。

不会的左转 oiwiki

题目传送门

P1339 [USACO09OCT]Heat Wave G

这一道题的本质其实就是在 dijkstra 中加一个计数就可以的，但一些题解讲得不是特别清楚。

    for(int j=1;j<=n;j++)
        {
            if(minn+a[p][j]<dis[j])
            {
                dis[j]=minn+a[p][j];
                sum[j]=sum[p];
            }
            else if(dis[j]==dis[p]+a[p][j])
                sum[j]+=sum[p];
        }

整个代码的核心就在这里。

首先 j 遍历的就是关于 p 连接的节点，如果我当前的最短路可以更新，证明 j 这个点就是在当前 p 的最短路往后一条边。 但就长远来说，dis[j] 不一定就是从起点到 j 的一个最短路,所以他的总方案数就继承了他原先的 sum[p] 的方案种数。

其次就是另外一个 else 他就是 p 和 j 完完全全连通了。

可以确定当前的就是最短路，直接加上去就可以了。

但是你可能会有这样的疑问，如果 p 走过的路和 j 重复了，会不会多算？

其实是不会的，因为我每次都是挑最优的去走，所以 sum[p] 就是有一些拐弯的地方更新而来的，所以不重复。

注意一开始要判重边。

所以完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N =2037;
const int maxn=1e6+10;
int a[N][N];
int dis[maxn],vis[maxn],sum[maxn],n,m;
void dijkstra(int s)
{
    int minn,p;
    memset(dis,0x3f3f3f3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    sum[s]=1;
    for(int i=1;i<=n;i++)
    {
        minn=1e6+10;
        for(int j=1;j<=n;j++)
        {
            if(!vis[j]&&minn>dis[j])
                p=j,minn=dis[j];
        }
        vis[p]=1;
        for(int j=1;j<=n;j++)
        {
            if(minn+a[p][j]<dis[j])
            {
                dis[j]=minn+a[p][j];
                sum[j]=sum[p];
            }
            else if(dis[j]==dis[p]+a[p][j])
                sum[j]+=sum[p];
        }
    }
}
int main()
{
    memset(a,1e6+10,sizeof(a));
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        cin>>u>>v>>w;
        if(a[u][v]>w)
            a[u][v]=w;
    }
    dijkstra(1);
    if(dis[n]==0x3f3f3f3f)
        cout<<"No answer";
    else
        cout<<dis[n]<<" "<<sum[n];
    return 0;
}

一个深痛的教训

所以同学们一定要看好数据范围！！！！！！（手动加感叹号）