我手动推了一下。。。发现WA了第一个点是因为4节点没有二次入队。。。但不知道如何去改**(是因为SPFA的特性吗!!?)**求大佬帮助orz (但是关于P1144这个几乎一样的题我写spfa却过了......) 下面是代码,判重边的操作应该没问题
#include<bits/stdc++.h>
using namespace std;
const int maxn=2005;
const int maxm=2e6+10;
const int mod =100003;
int head[maxm],dis[maxn],vis[maxn],dp[maxn];
int cnt;
/*
#define pr pair<int,int>
#define mp make_pair
priority_queue<pr,vector<pr>,greater<pr> > q;
*/
int v[maxn][maxn];
int n,m;
queue<int> q;
struct edge
{
int to,nxt,w;
}a[maxm];
void add(int x,int y,int w)
{
a[++cnt].nxt=head[x];
head[x]=cnt;
a[cnt].to=y;
a[cnt].w=w;
}
bool flag;
void SPFA()
{
memset(dis,0x3f,sizeof(dis));
// memset(vis,0,sizeof(vis));//注意清空
// for(int i=1;i<=n;i++)
// dis[i]=0x7fffffff;
dis[1]=0;
dp[1]=1;
vis[1]=1;
q.push(1);
while(!q.empty())
{
int u = q.front();
q.pop();
vis[u]=0;
if(u==n) flag=1;
for(int i=head[u];i;i=a[i].nxt)
{
int v=a[i].to;
if(dis[v]>dis[u]+a[i].w)
{
dis[v]=dis[u]+a[i].w;
dp[v]=dp[u];
if(!vis[v]) {q.push(v);vis[v]=1;}
}
else if(dis[v]==dis[u]+a[i].w)
{
dp[v]+=dp[u];
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
int x,y,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&x,&y,&w);
if(v[x][y]==0)
{
add(x,y,w);
v[x][y]=w;
}
else if(v[x][y]>w)
{
int j;
for (j=head[x];j&&a[j].to!=y;j=a[j].nxt) ;
a[j].w=w;
v[x][y]=w;
}
}
SPFA();
if(!flag) printf("No answer");
else
{
printf("%d %d\n",dis[n],dp[n]);
}
// for(int i=1;i<=n;i++)
// printf("%d ",dp[i]);
/*
5 5
1 2 1
2 3 1
3 4 1
4 5 1
1 4 3
输出:4 2
*/
return 0;
}