이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// 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;
struct Matrix {
ll d[5][5];
friend Matrix operator + (Matrix t1,Matrix t2) {
Matrix res;
for (int i=0;i<5;i++) for (int j=0;j<5;j++) {
res.d[i][j]=INF;
for (int k=0;k<5;k++) res.d[i][j]=min(t1.d[i][k]+t2.d[k][j],res.d[i][j]);
}
return res;
}
} tr[100010*4];
void change(int x,int l,int r,int root,Matrix A) {
if (l==r) { tr[root]=A; return; }
int mid=(l+r)>>1;
if (x<=mid) change(x,l,mid,root<<1,A);
else change(x,mid+1,r,root<<1|1,A);
tr[root]=tr[root<<1]+tr[root<<1|1];
}
void init(int i) {
if (i>=3&&i<=L); else return;
Matrix A;
for (int i=0;i<5;i++) for (int j=0;j<5;j++) A.d[i][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;
A.d[j][k]=mn[d[i-1]][d[i]][k];
}
change(i,3,L,1,A);
}
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]);
for (int i=3;i<=L;i++) init(i);
while (Q--) {
int x; read(x),read(d[x]);
init(x);
init(x-1);
init(x+1);
ll MN[5];
for (int i=0;i<5;i++) {
MN[i]=mn[d[1]][d[2]][i];
}
ll ans=INF;
if (L==2) {
for (int i=0;i<5;i++) ans=min(ans,MN[i]);
} else {
Matrix &res=tr[1];
for (int i=0;i<5;i++) for (int j=0;j<5;j++) ans=min(ans,MN[i]+res.d[i][j]);
}
if (ans==INF) ans=-1;
printf("%lld\n",ans);
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |