建设部网站13清单,企业免费推广网站,兰州网络推广与营销,如何建立自己的网站商城由题意可知#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
