燃烧火焰

· · 个人记录 

#include<bits/stdc++.h>
#define rep(i,j,k) for(ll i=(j),_i=(k);i<=_i;i++)
#define drp(i,j,k) for(ll i=(j),_i=(k);i>=_i;i--)
#define ll long long
#define Nx 100050
#define Mx 400050
using namespace std;
//---------------------------------//
ll read(){
    ll x=0,f=0;char ch;
    while(!isdigit(ch=getchar())) f|=ch=='-';
    while(isdigit(ch)) x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
    return f?-x:x;
}
//---------------------------------//
const ll inf=LONG_LONG_MAX;
const ll Mod=998244353;
ll n,m,k,mx,burn[Nx],po[25],S;
ll h[Nx],nxt[Mx],to[Mx],l[Mx],tot;
void add(ll u,ll v,ll w){
    nxt[++tot]=h[u],h[u]=tot,to[tot]=v,l[tot]=w;
}
ll _time[Nx],vis[Nx],sta[Nx];
typedef pair<ll,ll> P;
priority_queue<P,vector<P>,greater<P> > q;
void Dijkstra(ll E){
    rep(i,1,n) _time[i]=inf,vis[i]=0;
    rep(i,1,k) if(E&po[i-1]) {
        q.push(make_pair(0,burn[i]));
        _time[burn[i]]=0;
    }  
    while(q.size()){
        ll u=q.top().second;q.pop();
        if(vis[u]) continue;
        vis[u]=1;
        for(ll i=h[u];i;i=nxt[i]){
            ll v=to[i];
            if(_time[u]+l[i]<_time[v]){
                _time[v]=_time[u]+l[i];
                q.push(make_pair(_time[v],v));
            }
        }
    }
    if(mx==-1) rep(i,1,n) mx=max(mx,_time[i]);
    else rep(i,1,n) if(_time[i]<=mx) sta[i]+=E;
}
void init(){
    po[0]=1;
    rep(i,1,20) po[i]=po[i-1]*2;
}
ll quickpow(ll x,ll y){
    ll ret=1;
    while(y){
        if(y%2) ret=(ret*x)%Mod;
        x=(x*x)%Mod;
        y>>=1;
    }
    return ret;
}
ll f[1100000],del;
void dp(){
    rep(i,1,n) f[sta[i]]=1;
    rep(S,0,po[k]-1) if(f[S]){
        del++;
        rep(i,1,k) if(!(S&po[i-1])) 
            f[S+po[i-1]]=1;
    }
}
int main(){
    //freopen("flame.in","r",stdin);
    //freopen("flame.out","w",stdout);
    n=read(),m=read();
    init();
    rep(i,1,k=read()) burn[i]=read(),S+=po[i-1];
    rep(i,1,m){
        ll x=read(),y=read(),w=read();
        add(x,y,w),add(y,x,w);
    }
    mx=-1;
    Dijkstra(S);
    rep(i,1,k) Dijkstra(po[i-1]);
    dp();   
    printf("%lld",(po[k]-del)%Mod*quickpow(po[k],Mod-2)%Mod);
    return 0;   
}