题解 P2384 【最短路】

这是一道裸的 SPFA ，然而我交了 10+ 次才过。。。 注： memset 有毒。。。不到万不得已不要用。。。 附代码： ```cpp #include<iostream> #include<algorithm> #include<cstdio> #include<queue>//队列头文件 #include<cstring> #define MOD 9987 #define MAXN 1010 #define MAXM 10000010 #define MAX 99999999//最大值 using namespace std; int n,m,c=1,head[MAXN]; long long path[MAXN];//一定要开 long long,不然会炸。。。 bool vis[MAXN]; struct node{//边 int next,to,w; }a[MAXM]; inline int read(){//弱弱的读入优化。。。 int date=0,w=1;char c=0; while(c!='-'&&(c<'0'||c>'9')){if(c=='-')w=-1;c=getchar();} while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();} return date*w; } inline int relax(int u,int v,int w){//松弛操作 if(path[v]>(long long)path[u]*w){ path[v]=(path[u]*w);//乘积，不 mod 其实也行 return 1; } return 0; } void add(int u,int v,int w){//加边操作 a[c].to=v;a[c].w=w; a[c].next=head[u]; head[u]=c++; a[c].to=u;a[c].w=w; a[c].next=head[v]; head[v]=c++; } void spfa(){//开始工（gao）作（shi） int u,v; queue<int> q;//队列 q.push(1); path[1]=1;//一定要设为1，因为是乘积 vis[1]=true; while(!q.empty()){ u=q.front();//取队首 q.pop();//弹出 vis[u]=false; for(int i=head[u];i;i=a[i].next){ v=a[i].to; if(relax(u,v,a[i].w)&&!vis[v]){//松弛 vis[v]=true; q.push(v);//松弛成功则入队 } } } printf("%lld\n",path[n]%MOD);//输出 } int main(){ int u,v,w; memset(vis,false,sizeof(vis)); n=read();m=read(); for(int i=1;i<=n;i++)path[i]=MAX;//本来用的是 memset ，结果永久 WA 了一个点 for(int i=1;i<=m;i++){ u=read();v=read();w=read(); add(u,v,w);//加边 } spfa();//调用 return 0; ``` }//完美的结束。。。