原题：P10935

Dij 莫名奇妙 WA 了，建图和 Tarjan 没有似，懒得缩点就在原图跑。

把 Dij 换成 01bfs 就过了。

#include <iostream>
#include <queue>
using namespace std;
const int N=1e5+5;
int h[N],dis[N],vis[N],idx=0,n,m;
priority_queue<pair<int,int> > q;
#define ll long long
int stk[N],instk[N],top=0,cnt=0;
int dfn[N],low[N],scc[N],tot=0;
struct edge{int to,ne,wl;}e[N*3];
void add(int a,int b,int c){
	e[++idx]={b,h[a],c}; h[a]=idx;
}
void Tarjan(int x){
	dfn[x]=low[x]=++tot;
	stk[++top]=x;
	instk[x]=1;
	for(int i=h[x];i;i=e[i].ne){
		int y=e[i].to;
		if(!dfn[y]){
			Tarjan(y);
			low[x]=min(low[x],low[y]);
		}
		else if(instk[y])
			low[x]=min(low[x],dfn[y]);
	}
	if(dfn[x]==low[x]){
		int y=-1; ++cnt;
		while(x^y){
			y=stk[top--];
			instk[y]=0;
			scc[y]=cnt;
		}
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i) add(0,i,0);
	while(m--){
		int opt,x,y; scanf("%d%d%d",&opt,&x,&y);
		if(opt==1) add(x,y,0),add(y,x,0);
		if(opt==2) add(x,y,1);
		if(opt==3) add(y,x,0);
		if(opt==4) add(y,x,1);
		if(opt==5) add(x,y,0);
	}
	for(int i=1;i<=n;++i) if(!dfn[i]) Tarjan(i);
	for(int x=1;x<=n;++x) for(int i=h[x];i;i=e[i].ne)
		if(scc[x]==scc[e[i].to]&&e[i].wl) return !printf("-1\n"); 
	dis[0]=1;
	q.push({1,0});
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u]=1;
		for(int i=h[u];i;i=e[i].ne){
			int v=e[i].to;
			int w=e[i].wl;
			if(dis[u]+w>dis[v]){
				dis[v]=dis[u]+w;
				q.push({dis[v],v});
			}
		}
	}
	ll res=0;
	for(int i=1;i<=n;++i) res+=(ll)dis[i];
	printf("%lld\n",res);
}