제출 #656741

#제출 시각아이디문제언어결과실행 시간메모리
656741haojiandanWild Boar (JOI18_wild_boar)C++14
62 / 100
18053 ms469376 KiB
// wygzgyw #include <bits/stdc++.h> using namespace std; template <typename T> void read(T &t) { t=0; char ch=getchar(); int f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f; } template <typename T> void write(T t) { if (t<0) { putchar('-'); write(-t); return; } if (t>9) write(t/10); putchar('0'+t%10); } template <typename T> void writeln(T t) { write(t); puts(""); } #define MP make_pair typedef long long ll; const ll INF=1e18; const int maxn=4010; int n,m; int Q,L; ll dis[maxn][maxn],w[maxn]; pair<int,int> E[maxn]; ll mn[maxn][maxn][5]; pair<int,int> rem[maxn][maxn][5]; vector<int> in[maxn],out[maxn]; int id[maxn][maxn]; bool vis[maxn]; int d[maxn]; ll dp[2][maxn]; priority_queue<pair<ll,int>,vector<pair<ll,int> > ,greater<pair<ll,int> > > q; int main() { read(n),read(m); read(Q),read(L); int tot=0; for (int i=1;i<=m;i++) { int x,y; read(x),read(y); id[x][y]=id[y][x]=i; read(w[i]); E[tot]=MP(x,y); out[x].push_back(tot),in[y].push_back(tot); tot++; E[tot]=MP(y,x); out[y].push_back(tot),in[x].push_back(tot); tot++; } for (int i=0;i<tot;i++) { q.push(MP(0,i)); for (int j=0;j<tot;j++) dis[i][j]=INF,vis[j]=0; dis[i][i]=0; while (!q.empty()) { int x=q.top().second; q.pop(); if (vis[x]) continue; vis[x]=1; int u=E[x].second; for (int &id : out[u]) { int v=E[id].second; if ((id^x)==1) continue; assert(id!=x); ll w=::w[::id[u][v]]; assert(id/2+1==::id[u][v]); if (dis[i][id]>dis[i][x]+w) dis[i][id]=dis[i][x]+w,q.push(MP(dis[i][id],id)); } } } for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i!=j) { ll *mn=::mn[i][j]; pair<int,int> *rem=::rem[i][j]; for (int k=0;k<5;k++) mn[k]=INF; for (int k=0;k<5;k++) { for (int &x : out[i]) for (int &y : in[j]) { if (dis[x][y]+w[x/2+1]<mn[k]) { int A=E[x].second,B=E[y].first; if (k==1&&A==rem[0].first) continue; if (k==2&&(A==rem[0].first||B==rem[1].second)) continue; if (k==3&&B==rem[0].second) continue; if (k==4&&(B==rem[0].second||A==rem[3].first)) continue; mn[k]=dis[x][y]+w[x/2+1]; rem[k]=MP(A,B); } } if (id[i][j]&&w[id[i][j]]<mn[k]) { int A=j,B=i; if (k==1&&A==rem[0].first) continue; if (k==2&&(A==rem[0].first||B==rem[1].second)) continue; if (k==3&&B==rem[0].second) continue; if (k==4&&(B==rem[0].second||A==rem[3].first)) continue; mn[k]=w[id[i][j]]; rem[k]=MP(A,B); } } } for (int i=1;i<=L;i++) read(d[i]); while (Q--) { int x; read(x),read(d[x]); int op=0; for (int i=0;i<5;i++) dp[op][i]=mn[d[1]][d[2]][i]; // printf("%lld %d\n",mn[2][1][1],rem[2][1][1].second); for (int i=3;i<=L;i++) { for (int j=0;j<5;j++) dp[op^1][j]=INF; for (int j=0;j<5;j++) for (int k=0;k<5;k++) if (mn[d[i-1]][d[i]][k]<INF) { if (rem[d[i-2]][d[i-1]][j].second==rem[d[i-1]][d[i]][k].first) continue; dp[op^1][k]=min(dp[op^1][k],dp[op][j]+mn[d[i-1]][d[i]][k]); } op^=1; } ll ans=INF; for (int j=0;j<5;j++) ans=min(ans,dp[op][j]); if (ans==INF) ans=-1; printf("%lld\n",ans); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...