P1821 [USACO07FEB] Cow Party S题解

· · 个人记录

蒟蒻专属 只会朴素dijstra也能过！

题目传送门

首先分析题目，不难看出这是一道要求求最短路的题.

那么，因为数据范围的 1<=n<=1000，所以 Floyed 是行不通的，作为一个蒟蒻，剩下能用的只剩Dijstra了。

如果不会堆优化也没关系，我们多开一个数组就好了。

一 变量定义

#include<bits/stdc++.h>
#define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++)
#define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--)
using namespace std;
const int zhenli=0;//真理义父yyds
const int N=1005;
const int maxx=0x7fffff;
int n,m,x;
int dh[N][N];
int yy[N],fx[N],yz[N],hh[N]; 
int rm;
$maxx$ 不用多说，**但一定要开大** ~~(才没有因为开小了所以WA呢~~。 $dh$邻接矩阵存初始权值。 $yy$ $fx$ 分别存由 $x$ 出发和到 $x$ 的最小值。 $yz$ 作判断标记，$hh$ 存最终路径，$rm$ 为中间量 ------------ # 二 主体结构 输入，初始化等不用过多赘叙。 ``` fo(i,1,n) if(dh[x][i]<maxx)yy[i]=dh[x][i]; fo(i,1,n) if(dh[i][x]<maxx)fx[i]=dh[i][x]; warm(x); wazl(x); ``` 关键在于dij的函数部分。 我们大多牢记了dij的板子。 那么，多打一个不就好了吗。 只是注意，第二个函数中，赋初始值时是反向的。 ``` void warm(int x) { int y; yz[x]=1; fo(i,1,n-1) { rm=maxx; fo(j,1,n) if(yz[j]==0&&yy[j]<rm) { y=j; rm=yy[j]; } yz[y]=1; fo(j,1,n) if(yz[j]==0&&yy[j]>yy[y]+dh[y][j]) yy[j]=yy[y]+dh[y][j]; } } void wazl(int x) { int z; memset(yz,0,sizeof yz); yz[x]=1; fo(i,1,n-1) { rm=maxx; fo(j,1,n) if(yz[j]==0&&fx[j]<rm) { z=j; rm=fx[j]; } yz[z]=1; fo(j,1,n) if(yz[j]==0&&fx[j]>fx[z]+dh[j][z]) fx[j]=fx[z]+dh[j][z]; } } ``` ------------ # 最后 整合起来 完工 完整代码如下： ``` #include<bits/stdc++.h> #define fo(x,y,z) for(int (x)=(y);(x)<=(z);(x)++) #define fu(x,y,z) for(int (x)=(y);(x)>=(z);(x)--) using namespace std; const int zhenli=0; const int N=1005; const int maxx=0x7fffff; int n,m,x; int dh[N][N]; int yy[N],fx[N],yz[N],hh[N]; int rm; void warm(int x) { int y; yz[x]=1; fo(i,1,n-1) { rm=maxx; fo(j,1,n) if(yz[j]==0&&yy[j]<rm) { y=j; rm=yy[j]; } yz[y]=1; fo(j,1,n) if(yz[j]==0&&yy[j]>yy[y]+dh[y][j]) yy[j]=yy[y]+dh[y][j]; } } void wazl(int x) { int z; memset(yz,0,sizeof yz); yz[x]=1; fo(i,1,n-1) { rm=maxx; fo(j,1,n) if(yz[j]==0&&fx[j]<rm) { z=j; rm=fx[j]; } yz[z]=1; fo(j,1,n) if(yz[j]==0&&fx[j]>fx[z]+dh[j][z]) fx[j]=fx[z]+dh[j][z]; } } bool cmp(int a,int b) { return a>b; } int main() { scanf("%d%d%d",&n,&m,&x); fo(i,1,n) fo(j,1,n) dh[i][j]=maxx; memset(yy,0x3f,sizeof yy); memset(fx,0x3f,sizeof fx); fo(i,1,m) { int a,b,c; scanf("%d%d%d",&a,&b,&c); if(c<dh[a][b])dh[a][b]=c;//重边取短 } fo(i,1,n) if(dh[x][i]<maxx)yy[i]=dh[x][i]; fo(i,1,n) if(dh[i][x]<maxx)fx[i]=dh[i][x]; warm(x); wazl(x); fo(i,1,n) if(i!=x) { hh[i]=yy[i]+fx[i]; } sort(hh+1,hh+n+1,cmp); printf("%d",hh[1]); return zhenli; } ``` （我是食月的天狗$Qwq$。