北京做网站找哪家好,亚马逊关键词优化软件,腾讯云服务器怎么用,有口碑的番禺网站建设由题意可知#xff0c;我们需要求的是很多个点到同一个店的最短距离#xff0c;然后再求同一个点到很多个点的最短距离。 对于后者我们很好解决#xff0c;就是很经典的单源最短路径#xff0c;跑一边dijkstra或者SPFA即可。 然而对于前者#xff0c;我们应该怎么解决呢我们需要求的是很多个点到同一个店的最短距离然后再求同一个点到很多个点的最短距离。 对于后者我们很好解决就是很经典的单源最短路径跑一边dijkstra或者SPFA即可。 然而对于前者我们应该怎么解决呢难道我们需要求一边Floyd?当然不可能\(O(n^3)\)的时间复杂度对于我们的\(n1000\)是果断要超时的。 深入分析对于一张图A到B的最短距离应该等于B到A在反转一张图以后的最短距离。所谓反转一张图就是把变得方向调转。这一点是很显然的 因此对于问题一我们只需要把图反转然后求那个点到其它的最短距离即可。 #includecstdio
#includealgorithm
#includecstring
using namespace std;
#define rep(i,a,n) for(register int i(a);i(n);i)
#define per(i,a,n) for(register int i(a);i(n);--i)
#define fec(i,x) for(register int ihead[x];i;iNext[i])
#define debug(x) printf(debug:%s%d\n,#x,x)
#define mem(a,x) memset(a,x,sizeof(a))
templatetypename Ainline void read(Aa){a0;A f1;int c0;while(c0||c9){cgetchar();if(c-)f*-1;}while(c0c9){aa*10c-0;cgetchar();}a*f;}
templatetypename A,typename Binline void read(Aa,Bb){read(a);read(b);}
templatetypename A,typename B,typename Cinline void read(Aa,Bb,Cc){read(a);read(b);read(c);}const int maxn10007,maxm1000007,INF0x7f7f7f7f;
int u[maxm],v[maxm],w[maxm],Next[maxm],head[maxn],tot;
int u2[maxm],v2[maxm],w2[maxm],Next2[maxm],head2[maxn],tot2;
int n,m,p,x,y,z,ans;
int dist1[maxn],dist2[maxn];
bool visit[maxn];inline void addedge(int x,int y,int z){u[tot]x;v[tot]y;w[tot]z;Next[tot]head[x];head[x]tot;
}
inline void addedge2(int x,int y,int z){u2[tot2]x;v2[tot2]y;w2[tot2]z;Next2[tot2]head2[x];head2[x]tot2;
}void Dijkstra(int *u,int *v,int *w,int *head,int *Next,int *dist,int s){mem(visit,0);dist[s]0;rep(i,1,n){int MinINF,x;rep(i,1,n)if(!visit[i]dist[i]Min)Mindist[i],xi;visit[x]1;fec(i,x)if(!visit[v[i]]dist[v[i]]dist[x]w[i])dist[v[i]]dist[x]w[i];}
}void Init(){read(n,m,p);rep(i,1,m){read(x,y,z);addedge(x,y,z);addedge2(y,x,z); }
}void Work(){mem(dist1,0x7f);mem(dist2,0x7f);Dijkstra(u,v,w,head,Next,dist1,p);Dijkstra(u2,v2,w2,head2,Next2,dist2,p);rep(i,1,n)ansmax(ans,dist1[i]dist2[i]);printf(%d\n,ans);
}int main(){Init();Work();return 0;
} 转载于:https://www.cnblogs.com/hankeke/p/USACO07FEB-Silver_Cow_Party.html
