CF843D Dynamic Shortest Path spfa+剪枝

考试的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
"); 
            }
            else
            { 
                if(!flag) 
                {
                    flag=1; 
                    dijkstra();       
                }     
                printf("%lld
",d[pp]);
            }        
        }
    }
    // printf("%d
",clock()-t);    
    return 0; 
}