1 条题解
-
0
C++ :
#pragma GCC optimize ("O2") #include <bits/stdc++.h> #define inf 0x3f3f3f3f #define met(a,b) memset(a,b,sizeof a) #define pb push_back #define mp make_pair #define rep(i,l,r) for(int i=(l);i<=(r);++i) #define inf 0x3f3f3f3f using namespace std; typedef long long ll; const int N = 1e3+50;; const int M = 6e5; const int mod = 19260817; const int mo=123; const double pi= acos(-1.0); typedef pair<int,int>pii; int n,m,S,T; ll dis[N],dp[2][N]; int vis[N],mark[N]; vector<pii>edg[N]; ll spfa(int s,int t,ll x){ for(int i=0;i<N;i++)dis[i]=1e18,vis[i]=0; queue<int>q; vis[s]=1; dis[s]=0; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=0;i<edg[u].size();i++){ int v=edg[u][i].first; int w=edg[u][i].second; if(!mark[v])continue; if(dis[v]>dis[u]+x+w){ dis[v]=dis[u]+x+w; if(!vis[v]){ q.push(v); vis[v]=1; } } } } return dis[t]; } void spfa2(int s,ll x){ int ty=(s==S); for(int i=0;i<N;i++)dp[ty][i]=1e18,vis[i]=0; queue<int>q; vis[s]=1; dp[ty][s]=0; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(int i=0;i<edg[u].size();i++){ int v=edg[u][i].first; int w=edg[u][i].second; if(dp[ty][v]>dp[ty][u]+x+w){ dp[ty][v]=dp[ty][u]+x+w; if(!vis[v]){ q.push(v); vis[v]=1; } } } } } bool check(ll x){ //x=3; ll len1=spfa(S,T,x); spfa2(S,x); spfa2(T,x); ll len2=1e18; for(int i=1;i<=n;i++){ if(mark[i])continue; //printf("%lld %lld\n",dp[1][i],dp[0][i]); len2=min(len2,dp[1][i]+dp[0][i]); } //printf("len1:%lld len2:%lld\n",len1,len2); // system("pause"); if(len1>len2)return false; return true; } int main(){ int TT; scanf("%d",&TT); while(TT--){ met(mark,0); for(int i=0;i<N;i++)edg[i].clear(); scanf("%d%d%d%d",&n,&m,&S,&T); while(m--){ int u,v,w; scanf("%d%d%d",&u,&v,&w); edg[u].pb(mp(v,w)); edg[v].pb(mp(u,w)); } int k; scanf("%d",&k); while(k--){ int u; scanf("%d",&u); mark[u]=1; } ll l=0,r=1e15,ans=-1; while(l<=r){ ll mid=(l+r)/2; //printf("mid:%lld\n",mid); if(check(mid))l=mid+1,ans=mid; else r=mid-1; } if(ans==-1)puts("Impossible"); else if(ans==1e15)puts("Infinity"); else { ll res=ans; for(int i=1;i<=5;i++){ if(check(res+i))ans=res+i; } printf("%lld\n",ans); } } return 0; }
- 1
信息
- ID
- 1031
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- (无)
- 标签
- 递交数
- 0
- 已通过
- 0
- 上传者