题解 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哦