题解 P1608 【路径统计】

· · 题解

这道题我做了好久……WA+TLE+RE+MLE……

好了,下面开始讲:

首先,我按照p1144来打,结果WA了五个点:

#include<bits/stdc++.h>
using namespace std;
priority_queue<pair<long long,long long> >q;//大根堆,d数组取负转为小根堆;
long long n,m,s,i,cnt,x,y,z,he[1000001],ne[2000001],l[2000001],to[2000001],d[1000001],ans[1000001];
bool b[1000001];
int main()
{
    scanf("%lld%lld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        cnt++;
        ne[cnt]=he[x];
        to[cnt]=y;
        l[cnt]=z;
        he[x]=cnt;
    }//邻接表读入
    memset(d,127,sizeof(d));
    ans[1]=1;
    d[1]=0;
    q.push(make_pair(0,1));
    while (q.size())
    {
        x=q.top().second;
        q.pop();
        if (b[x]) continue;
        b[x]=true;
        for (i=he[x];i!=0 ;i=ne[i])
            if (d[to[i]]>d[x]+l[i])
            {
                d[to[i]]=d[x]+l[i];
                ans[to[i]]=ans[x];
                q.push(make_pair(-d[to[i]],to[i]));
            }
            else if (d[to[i]]==d[x]+l[i])
                ans[to[i]]=(ans[to[i]]+ans[x]);
    }
    if (ans[n]==0) printf("No answer");
    else printf("%lld %lld",d[n],ans[n]);
    return 0;
}

(做ans的一段详见这里)

54分,原因大家也都知道,未判重 那么我就想到,n<=2000;是不是可以上暴力呢?

于是我用二维数组p来存放长度,打了一遍非优化版单源最短路:

#include<bits/stdc++.h>
using namespace std;
long long j,p[2001][2001],n,m,s,i,cnt,x,y,z,d[2001],min1,ans[100001];
bool b[1000001];
int main()
{
    scanf("%lld%lld",&n,&m);
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
        p[i][j]=-1;//初始化
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        p[x][y]=z;//长度覆盖
    }
    for (i=0;i<=n;i++) d[i]=1e9;
    ans[1]=1;
    d[1]=0;
    for (i=1;i<=n;i++)
    {
        min1=0;
        for (j=1;j<=n;j++)
            if (d[j]<d[min1]&&!b[j]) min1=j;
        b[min1]=true;
        for (j=1;j<=n;j++)
        if (p[min1][j]==-1) continue;
        else
            if (d[j]>d[min1]+p[min1][j])
            {
                d[j]=d[min1]+p[min1][j];
                ans[j]=ans[min1];
            }
            else if (d[j]==d[min1]+p[min1][j])
                ans[j]=(ans[j]+ans[min1]);
    }
    if (ans[n]==0) printf("No answer");
    else printf("%lld %lld",d[n],ans[n]);
    return 0;
}

然而又凉凉……第九个点WA掉了……

于是我又想,有些边不是重边啊……于是(省略500+个字)最后决定将q数组开成结构体,其中b数组存储从x到y有几条边,a数组存储各边边长,最后……MLE了……

最后通过压缩数组成功AC:

#include<bits/stdc++.h>
using namespace std;
long long j,n,m,s,i,cnt,x,y,z,d[2001],min1,ans[2001],k;
struct as{
    int a[5],b;//开到10就MLE
}p[2001][2001];
bool b[2001],b1;//结构体
int main()
{
    scanf("%lld%lld",&n,&m);
    for (i=1;i<=m;i++)
    {
        scanf("%lld%lld%lld",&x,&y,&z);
        b1=true;
        for (k=1;k<=p[x][y].b;k++)
        if (p[x][y].a[k]==z) b1=false;
        if (b1) 
        {
            p[x][y].b++;
            p[x][y].a[p[x][y].b]=z;//加边
        }
    }
    for (i=0;i<=n;i++) d[i]=1e9;
    ans[1]=1;
    d[1]=0;
    for (i=1;i<=n;i++)
    {
        min1=0;
        for (j=1;j<=n;j++)
            if (d[j]<d[min1]&&!b[j]) min1=j;
        b[min1]=true;
        for (j=1;j<=n;j++)
            for (k=1;k<=p[min1][j].b;k++)
        if (p[min1][j].a[k]==-1) continue;
        else
            if (d[j]>d[min1]+p[min1][j].a[k])
            {
                d[j]=d[min1]+p[min1][j].a[k];
                ans[j]=ans[min1];
            }
            else if (d[j]==d[min1]+p[min1][j].a[k])
                ans[j]=(ans[j]+ans[min1]);
    }
    //for (i=1;i<=n;i++)
    //  printf("%lld %lld\n",d[i],ans[i]);
    if (ans[n]==0) printf("No answer");
    else printf("%lld %lld",d[n],ans[n]);
    return 0;
}

结束,注意加了反抄题解代码,会CE哦