题解 P2299 【Mzc和体委的争夺战】

# 显而易见的一道单源最短路~~裸题~~ 题目就没什么可以解释的了，毕竟都看得出来是最短路 但是这个题目有坑啊 好吧现在我不说 ## 代码 ``` //Shikita #include<iostream> #include<queue> #include<cstdio> #include<cstring> using namespace std; const int N=2505,M=400005; int head[N],ver[M],edge[M],Next[M],d[N],f[2505][2505]; bool v[N]; int n,m,tot; struct node{int x,y;}ff; queue<node>qq; priority_queue< pair<int ,int> > q; int read() { int x=0,w=1;char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*w; } void add(int x,int y,int z) { ver[++tot]=y,edge[tot]=z,Next[tot]=head[x],head[x]=tot; } void dijkstra() { memset(d,0x3f,sizeof(d)); memset(v,0,sizeof(v)); d[1]=0; q.push(make_pair(0,1)); while(q.size()) { int x=q.top().second; q.pop(); if(v[x]) continue; v[x]=1; for(int i=head[x];i;i=Next[i]) { int y=ver[i],z=edge[i]; if(d[y]>d[x]+z) { d[y]=d[x]+z; q.push(make_pair(-d[y],y)); } } } } int main() { n=read(),m=read(); for(int i=1;i<=m;i++) { int x=read(),y=read(),z=read(); if(f[x][y]==0) { f[x][y]=z; ff.x=x,ff.y=y; qq.push(ff); } else f[x][y]=min(f[x][y],z); } while(!qq.empty()) { ff=qq.front();qq.pop(); add(ff.x,ff.y,f[ff.x][ff.y]); add(ff.y,ff.x,f[ff.x][ff.y]); } dijkstra(); cout<<d[n]<<endl; } ``` 我们需要判重！！！！！！ 因为数据的原因，如果不判重会WA第二个和第十个点 虽然我也不知道为什么 而且我的判重也非常丑陋。。。 好吧各位大佬就多多包含吧