记录编号	578512	评测结果	AAAAAAAAAA
题目名称	[SCOI2011] 糖果	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.400 s
提交时间	2023-03-23 08:38:01	内存使用	8.29 MiB

#include <bits/stdc++.h>
#define pb emplace_back
using pii = std::pair<int,int>;

const int maxn = 1e5 + 5;
std::vector<pii> G[maxn];
int n,m,dis[maxn],num[maxn];
std::deque<int> q;
bool vis[maxn];

bool SPFA(int s) {
    memset(dis , -0x3f , sizeof(dis));
    vis[s] = true;
    dis[s] = 1;
    q.push_back(s);
    while(!q.empty()) {
        int u = q.front();
        q.pop_front();
        vis[u] = false;
        for(auto& [v , w] : G[u])
            if(dis[v] < dis[u] + w) {
                dis[v] = dis[u] + w;
                ++ num[v];
                if(num[v] == n)
                    return false;
                if(!vis[v]) {
                	if(q.empty())
						q.push_back(v);
					else {
						if(dis[q.front()] < dis[v])
							q.push_front(v);
						else
							q.push_back(v);
					} 
                    vis[v] = true;
                }
            }
    }
    return true;
}

int main() {
	freopen("tangguo.in","r",stdin);
	freopen("tangguo.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(int i = 1;i <= m;++ i) {
        int op,u,v;
        scanf("%d %d %d",&op,&u,&v);
        if(u == v&&(~ op & 1))
        	return puts("-1"),0;
        switch(op) {
            case 1 : {
                G[u].pb(v , 0);
                G[v].pb(u , 0);
                break ;
            }
            case 2 : {
                G[u].pb(v , 1);
                break ;
            }
            case 3 : {
                G[v].pb(u , 0);
                break ;
            }
            case 4 : {
                G[v].pb(u , 1);
                break ;
            }
            case 5 : {
                G[u].pb(v , 0);
                break ;
            }
        }
    }
    for(int i = 1;i <= n;++ i)
        G[0].pb(i , 0);
    if(!SPFA(0)) {
        puts("-1");
        return 0;
    }
    long long ans = 0;
    for(int i = 1;i <= n;++ i)
        ans += dis[i];
    printf("%lld\n",ans);
    return 0;
}