考试的T3,拿暴力+剪枝卡过去了.
没想到 CF 上也能过 ~
code:
#include <bits/stdc++.h> #define N 100004 #define LL long long #define inf 1000000000000000 using namespace std; int go[N]; namespace IO { char *p1, *p2, buf[100000]; #define nc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1 ++ ) inline int rd() { int x = 0; char c = nc(); while (c < 48) { c = nc(); } while (c > 47) { x = (((x << 2) + x) << 1) + (c ^ 48), c = nc(); } return x; } inline void setIO(string s) { string in=s+".in"; string out=s+".out"; freopen(in.c_str(),"r",stdin); freopen(out.c_str(),"w",stdout); } }; LL d[N]; vector<int>G[N]; int n,m,Q,done[N],inq[N]; struct edge { LL val; int u,v; }ee[N]; deque<int>q; void dijkstra() { for(int i=1;i<=n;++i) d[i]=inf,inq[i]=0; d[1]=0, inq[1]=1; q.push_back(1); while(!q.empty()) { int u=q.front(); q.pop_front(); for(int i=G[u].size()-1;i>=0;--i) { edge e=ee[G[u][i]]; inq[e.u]=0; if(d[e.v]>d[u]+e.val) { d[e.v]=d[u]+e.val; if(!inq[e.v]) { if(q.empty()||d[e.v]<d[q.front()]) q.push_front(e.v); else q.push_back(e.v); inq[e.v]=1; } } } } } int main() { // int t=clock(); // IO::setIO("input"); int i,j,flag=1; n=IO::rd(); m=IO::rd(); Q=IO::rd(); // scanf("%d%d%d",&n,&m,&Q); for(i=1;i<=m;++i) { ee[i].u=IO::rd(); ee[i].v=IO::rd(); ee[i].val=IO::rd(); G[ee[i].u].push_back(i); } dijkstra(); for(i=1;i<=n;++i) if(d[i]==inf) go[i]=0; else go[i]=1; for(i=1;i<=Q;++i) { int opt,pp; opt=IO::rd(); pp=IO::rd(); // scanf("%d%d",&opt,&pp); if(opt==2) { for(j=1;j<=pp;++j) { int x=IO::rd(); ++ee[x].val; } flag=0; } else { if(!go[pp]) { printf("-1\n"); } else { if(!flag) { flag=1; dijkstra(); } printf("%lld\n",d[pp]); } } } // printf("%d\n",clock()-t); return 0; }