Elaxia의 노선 문제풀이
Elaxia의 노선 문제풀이
두 그룹의 가장 짧은 경로의 가장 긴 공공 경로를 먼저 정도 반도를 구하고 두 그룹의 가장 짧은 경로 트리를 구한 다음에 한 그룹의 가장 짧은 경로 트리에 토폴로지를 하고 다른 가장 짧은 경로 트리는 같은 변이 존재할 때 dp를 업데이트한다.
#include
using namespace std;
const int N=1500;
int n,m,s1,s2,t1,t2,p1,p2,p3,cnt=0,cnt2=0,ans=0,dp[N],rd[N],head[N],head2[N],dis[4][N];
struct edge{int nxt,to,w,v;}e[N*N],f[N*N];
struct xd{
int z,i;
bool operator < (const xd &a) const {return z>a.z;}
}tmp,nw;
priority_queue q;
inline void add(int u,int v,int w){e[++cnt].nxt=head[u],e[cnt].to=v,e[cnt].w=w,head[u]=cnt;}
inline void add2(int u,int v,int w){f[++cnt2].nxt=head2[u],f[cnt2].to=v,f[cnt2].w=w,head2[u]=cnt2,++rd[v];}
inline int read(){
int T=0,F=1; char ch=getchar();
while(ch'9'){if(ch=='-') F=-1; ch=getchar();}
while(ch>='0'&&ch<='9') T=(T<<3)+(T<<1)+(ch-48),ch=getchar();
return F*T;
}
void dijkstra(int x,int y){
dis[x][y]=0,tmp.i=y,tmp.z=0,q.push(tmp);
while(!q.empty()){
tmp=q.top(),q.pop();
if(dis[x][tmp.i]nw.z) dis[x][nw.i]=nw.z,q.push(nw);
}
}
}
void tppx(){
queue qq; int tt; cnt=0;
for(int i=1;i<=n;++i) if(!rd[i]) qq.push(i);
while(!qq.empty()){
tt=qq.front(),qq.pop(),ans=max(dp[tt],ans),head[++cnt]=tt;
for(int i=head2[tt];i;i=f[i].nxt){
--rd[f[i].to];
if(dis[2][tt]+f[i].w+dis[3][f[i].to]==p2) dp[f[i].to]=max(dp[f[i].to],dp[tt]+f[i].w);
if(!rd[f[i].to]) qq.push(f[i].to);
}
}
memset(dp,0,sizeof(dp));
for(int i=cnt;i>=1;--i){for(int j=head2[head[i]];j;j=f[j].nxt) if(dis[2][f[j].to]+f[j].w+dis[3][head[i]]==p2) dp[head[i]]=max(dp[head[i]],dp[f[j].to]+f[j].w); ans=max(ans,dp[head[i]]);}
}
int main(){
n=read(),m=read(),s1=read(),t1=read(),s2=read(),t2=read();
for(int i=1;i<=m;++i) p1=read(),p2=read(),p3=read(),add(p1,p2,p3),add(p2,p1,p3);
memset(dis,0x3f,sizeof(dis)),dijkstra(0,s1),dijkstra(1,t1),dijkstra(2,s2),dijkstra(3,t2),p1=dis[0][t1],p2=dis[2][t2];
for(int j=1;j<=n;++j) for(int i=head[j];i;i=e[i].nxt) if(dis[0][j]+e[i].w+dis[1][e[i].to]==p1) add2(j,e[i].to,e[i].w);
tppx(),printf("%d
",ans);
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.