大陆争霸（ 最短路变形）

题目链接：https://www.luogu.org/problemnew/show/P2446

最短路变形，用dis数组记录到达的最短路，用dis2数组记录可以通过的最短路

算是加强了对迪杰斯特拉算法的理解吧=-=之前一直用dis数组去更新新边，其实应该用struct里面的v来更新新边=-=wa了好多次...

代码：

#include<cstdio>
#include<cstdlib>
#include<vector>
#include<cstring>
#include<queue> 
using namespace std;
const int N=70050;
struct node{
    int nu,v,ne;
}edge[N*2];
struct node2{
    int nu,v;
    bool operator<(const node2&other)const{
        return v>other.v;
    }
};
int head[N/20],dis[N/20],cnt[N/20],dis2[N/20];
bool vis[N/20];
int tot,n,m;
vector<int>g[N/20];
void add(int a,int b,int c){
    edge[++tot].nu=b;
    edge[tot].v=c;
    edge[tot].ne=head[a];
    head[a]=tot;
}
void solve(){
    priority_queue<node2>q;
    q.push((node2){1,0});
    dis[1]=0;
    dis2[1]=0;
    while(!q.empty()){
        node2 a=q.top();
        q.pop();
        if(vis[a.nu])continue;
        vis[a.nu]=true;
        for(int i=head[a.nu];i!=-1;i=edge[i].ne){
            int k=edge[i].nu;
            if(dis[k]>a.v+edge[i].v){
                dis[k]=a.v+edge[i].v;
                if(!cnt[k]) q.push((node2){k,max(dis[k],dis2[k])});
            }
        }
        for(int i=0;i<g[a.nu].size();i++){
            int p=g[a.nu][i];
            cnt[p]--;
            dis2[p]=max(dis2[p],a.v);
            if(!cnt[p])q.push((node2){p,max(dis2[p],dis[p])});
        }
    }
 } 
int main(){
    scanf("%d%d",&n,&m);
    memset(head,-1,sizeof(head));
    memset(dis,0x3f,sizeof(dis)); 
    for(int i=1;i<=m;i++){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        if(a!=b)
            add(a,b,c);
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&cnt[i]);
        for(int j=1;j<=cnt[i];j++){
            int a;
            scanf("%d",&a);
            g[a].push_back(i);
        }
    }
    solve();
    printf("%d
",max(dis[n],dis2[n]));
}