2021/2/1
今天完成的题（SPFA优化全部，差分约束全部，tarjan(剩两个)(最后一个为新知识 (2-SAT) )）
- 双调路径
- 虫洞
- 最小圈
- Easy SSSp
- 方伯伯运椰子
- Interval
- 出纳员问题
- 糖果
- 布局 latout
- 受欢迎的牛
- 最大强联通子图
- 网络协议
- 消息的传递
- 网络间谍
/*
树状数组优化版本SPFA
*/
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define N 1100
#define M 3100
#define C 10010
using namespace std;
const int A = 1e5 + 11;
const int B = 2050;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n,m,s,t,head[N],cnt=0,dis[N][C],tree[N][C];
bool vis[N][C];
struct node{
int v,nxt ;
int w1;
int w2;
} ed[B << 1];
void add(int u, int v, int c, int t){
ed[++cnt].nxt = head[u];
ed[cnt].v = v;
ed[cnt].w1 = c;
ed[cnt].w2 = t;
head[u] = cnt;
return;
}
int lowbit(int x) {return x & (-x);}
void change(int x, int y, int z){
y++;
while(y < 10100){
tree[x][y] = min(tree[x][y], z);
y += lowbit(y);
}
return;
}
int ask(int x, int y){
y++;
int mn = 0x7fffffff;
while(y >= 1){
mn = min(mn, tree[x][y]);
y -= lowbit(y);
}
return mn;
}
void spfa(){
queue<pair<int,int> > q;
memset(dis, 0x3f, sizeof(dis));
memset(tree, 0x3f, sizeof(tree));
memset(vis, 0, sizeof(vis));
dis[s][0] = 0;
vis[s][0] = 1;
q.push(make_pair(s, 0));
change(s, 0, 0);
while(!q.empty()){
int w = q.front().second, u = q.front().first;
q.pop();
vis[u][w] = 0;
for(int i = head[u]; i; i = ed[i].nxt){
int v = ed[i].v, w1 = ed[i].w1, w2 = ed[i].w2;
int ww = w + w1;
if(ask(v,ww) > dis[u][w] + w2)
{
dis[v][ww] = dis[u][w] + w2;
change(v, ww, dis[v][ww]);
if(!vis[v][ww]){
q.push(make_pair(v,ww));
vis[v][ww] = 1;
}
}
}
}
return;
}
int main() {
// freopen(".in", "r", stdin);
// freopen("cc.out", "w", stdout);
cin >> n >> m >> s >> t;
for (int i = 1; i <= m; i++){
int u, v, w1, w2;
cin >> u >> v >> w1 >> w2;
add(u, v, w1, w2);
add(v, u, w1, w2);
}
spfa();
int minx = 0x3f3f3f3f, ans = 0;
for (int i = 1; i <= 10000; i++) {
//cout << dis[t][i] << endl;
if (dis[t][i] < minx)
minx = dis[t][i], ans++;
// cout << minx << endl;
}
printf("%d
",ans);
fclose(stdin);
fclose(stdout);
return 0;
}
//板子
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define eps 1e-12
using namespace std;
const int A = 1e5 + 11;
const int B = 100005;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int v, nxt, w;
} e[B << 1];
int t, head[B], cnt, vis[B], dis[B], n, m, k, flag = 0;
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
bool spfa(int s){
vis[s] = 1;
for(int i = head[s]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if(dis[v] > dis[s] + w)
{
dis[v] = dis[s] + w;
if(vis[v] || spfa(v)) return 1;
}
}
vis[s] = 0;
return 0;
}
int main() {
// freopen("dd.in", "r", stdin);
// freopen(".out", "w", stdout);
t = read();
while(t--)
{
memset(vis, 0, sizeof(vis));
memset(dis, 0, sizeof(dis));
memset(head, 0, sizeof(head));
cnt = 0;
n = read(), m = read(), k = read();
int a, b, c;
for (int i = 1; i <= m ; i++)
{
cin >> a >> b >> c;
add(a, b, c);
add(b, a, c);
}
for (int i = 1; i <= k; i++)
{
cin >> a >> b >> c;
add(a, b, -c);
}
flag = 0;
for(int i = 1;i <= n; i++)
{
if(spfa(i))
{
flag = 1;
break;
}
}
if(flag) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}
/*
错误： 边表数据类型int 代替 double
SPFA数据类型 int 代替 double
二分 定义类型错误
*/
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define eps 1e-12
using namespace std;
const int A = 1e5 + 11;
const int B = 10005;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
bool vis[B];
int m, cnt, head[B], k, nxt[B], to[B];
double ww[B];
double dis[B];
void add(int u, int v, double w){
nxt[++cnt] = head[u];
to[cnt] = v;
ww[cnt] = w;
head[u] = cnt;
}
bool dfs(int u, double lim){
vis[u] = 1;
for (int i = head[u]; i; i = nxt[i]){
int v = to[i];
if(dis[v] > dis[u] + ww[i] - lim){
dis[v] = dis[u] + ww[i] - lim;
if(vis[v] ||dfs(v, lim)) return 1;
}
}
vis[u] = 0;
return 0;
}
bool check(double lim){
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= k; i++) dis[i] = 0;
for (int i = 1; i <= k; i++){
if(dfs(i, lim)) return 1;
}
return 0;
}
int main() {
//freopen("dd.in", "r", stdin);
// freopen(".out", "w", stdout);
cin >> k >> m;
for (int i = 1; i <= m; i++){
int u, v;
double s;
scanf("%d %d %lf", &u, &v, &s);
add(u, v, s);
}
double l = -1e7, r = 1e7;
while(r - l > eps ){
double mid = (l + r) / 2.0;
if(check(mid)) r = mid ;
else l = mid ;
}
printf("%.8lf
", r);
return 0;
}
//板子
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define eps 1e-12
using namespace std;
const int A = 1e5 + 11;
const int B = 100005;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int v, nxt, w;
} e[B << 1];
int t, head[B], cnt, vis[B], dis[B], n, m, k, flag = 0;
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
bool spfa(int s){
vis[s] = 1;
for(int i = head[s]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if(dis[v] > dis[s] + w)
{
dis[v] = dis[s] + w;
if(vis[v] || spfa(v)) return 1;
}
}
vis[s] = 0;
return 0;
}
int main() {
freopen("dd.in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read(), k = read();
int a, b, c;
for (int i = 1; i <= m ; i++)
{
cin >> a >> b >> c;
add(a, b, c);
}
memset(dis, 0x3f, sizeof(dis));
dis[k] = 0;
if(spfa(k))
{
flag = 1;
}
if(head[1] == 0) flag = 1;
if(flag) cout << -1 << endl;
else{
for (int i = 1;i <= n; i++)
if(dis[i] == 1061109567)
cout <<"NoPath" << endl;
else cout<< dis[i] << endl;
}
return 0;
}
/*
P3288 [SCOI2014]方伯伯运椰子
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define N 5010
#define INF 0x3f3f3f3f
#define db double
using namespace std;
int n,m,bb,T;
db l,r,mid,d[N];
struct Bn
{
int from,to;
db quan;
}bn[10010],tmp[10010];
inline void add(int u,int v,int w)
{
bb++;
bn[bb].to=v;
bn[bb].from=u;
bn[bb].quan=(db)w;
}
inline bool check(db u)
{
int i,j;
bool have;
for(i=1;i<=bb;i++) tmp[i].quan+=u;
d[1]=0;
for(i=2;i<=n+2;i++) d[i]=INF;
for(i=1;i<=n+2;i++)
{
have=0;
for(j=1;j<=bb;j++)
{
if(d[tmp[j].to]>d[tmp[j].from]+tmp[j].quan)
{
have=1;
d[tmp[j].to]=d[tmp[j].from]+tmp[j].quan;
}
}
if(!have) return 0;
}
return 1;
}
int main()
{
int i,j,p,q,o,a,b,c,d;
cin>>n>>m;
for(i=1;i<=m;i++)
{
scanf("%d%d%d%d%d%d",&p,&q,&a,&b,&c,&d);
if(c) add(q,p,a-d);
add(p,q,b+d);
}
for(l=0,r=10000,T=200;T;T--)
{
for(i=1;i<=bb;i++) tmp[i]=bn[i];
mid=(l+r)/2;
check(mid)?l=mid:r=mid;
}
printf("%.2lf",l);
}
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int nxt, v, w;
} e[B << 1];
int l, r;
int s[B], vis[B], cnt, dis[B], n, m, head[B], use[B], t, num[B];
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
queue<int> q;
int spfa(int s){
memset(vis, 0, sizeof(vis));
memset(dis, 0x3f, sizeof(dis));
memset(use, 0, sizeof(use));
dis[s] = 0, vis[s] = 1, q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
use[u]++;
if(use[u] > n) return -1;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if(dis[v] > dis[u] + w){
dis[v] = dis[u] + w;
//use[i]++;
//if(use[i] > n - 1) return 0;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
if(dis[n] > 1e8)
return -2;
return dis[n];
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), l = read(), r = read();
int a, b, c;
for (int i = 1; i <= l; i++){
cin >> a >> b >> c;
add(a, b, c);
}
for (int i = 1; i <= r; i++){
cin >> a >> b >> c;
add(b, a, -c);
}
memset(dis, 0x3f,sizeof(dis));
for(int i = 1; i <= n; i++){
add(0, i, 0);
}
for(int i = 1; i < n; i++)
{
add(i + 1, i, 0);
}
int sp = spfa(0);
if(sp <= -1){
cout << sp;
return 0;
}
else cout << spfa(1) << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
/*
不要用边表！！！！！！！！！！
定义类型不要错！！！！！
尤其是 tarjan void!!!!!!!!!!
*/
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int manx = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
vector<int> e[11000];
int zxs,head[manx],cnt,headd[manx],n,m,low[manx],lt[manx],dfs[manx],js,top,st[manx],cl[manx],zbc;
int id[manx],cd[manx];
int siz[manx];
int ans,sbw;
/*----------------------------*/
void tarjan(int u){
low[u] = dfs[u] = ++js; st[++top] = u;
for (int i = 0; i < e[u].size(); i++)
{
int v =e[u][i];
if(!dfs[v]) { tarjan(v); low[u] = min(low[u], low[v]);}
else if(!lt[v])
{
low[u] = min(low[u], dfs[v]);
}
}
if(dfs[u] == low[u])
{
lt[u] = zxs++;
while(st[top] != u){ siz[zxs]++; lt[st[top--]] = zxs; }
siz[zxs]++;
lt[st[top--]] = zxs;
}
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= m; i++)
{
int x, y;
cin >> x >> y;
e[x].push_back(y);
}
for (int i = 1; i <= n; i++) if(!dfs[i]) tarjan(i);
for (int i = 1; i <= n; i++)
for(int j = 0; j < e[i].size(); j++)
{
int v = e[i][j];
if(lt[i] != lt[v])
{
cd[lt[i]]++;
}
}
int k = 0;
for (int i = 1; i <= zxs; i++)
if(!cd[i])
{
if(k){ cout << "0"; return 0;}
k = i;
}
cout << siz[k] << endl;
return 0;
}
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int nxt, v, w;
} e[B << 1];
int r[B],s[B], vis[B], cnt, dis[B], n, m, head[B], t, num[B];
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
bool check(int lim){
memset(head, 0, sizeof(head));
memset(dis, 0, sizeof(dis));
memset(vis, 0, sizeof(vis));
cnt = 0;
add(0, 24, lim);
for (int i = 1; i <= 24; i++){
add(i - 1, i, 0);
add(i, i - 1, -num[i]);
if(i > 8) add(i - 8, i, r[i]);
else add(i + 16, i, r[i] - lim);
}
queue<int> q;
q.push(0), dis[0] = 0, vis[0] = 0;
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if(dis[v] < dis[u] + w){
dis[v] = dis[u] + w;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
return dis[24] == lim;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
t = read();
while(t--){
memset(num, 0, sizeof(num));
for (int i = 1; i <= 24; i++) r[i] = read();
n = read();
for (int i = 1; i <= n ; i++){
int x = read() + 1;
num[x]++;
}
int l = 0, r = n, ans = 0;
while(l <= r){
int mid = (r + l) >> 1;
if(check(mid)) ans = mid, r = mid - 1;
else l = mid + 1;
}
if(ans == inf) cout << "No Solution" << endl;
else cout << ans << endl;
}
fclose(stdin);
fclose(stdout);
return 0;
}
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int v, nxt, w;
} e[B];
int vis[B], dis[B];
int head[B], cnt, n, m, minx = inf, manx = -inf;
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
void spfa(int s){
memset(vis, 0, sizeof(vis));
memset(dis, -inf, sizeof(dis));
queue<int> q;
dis[s] = 0, vis[s] = 1, q.push(s);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
for (int i = head[u]; i; i = e[i].nxt){
int v = e[i].v, w = e[i].w;
if(dis[v] < dis[u] + w)
{
dis[v] =dis[u] + w;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
m = read();
while(m--){
memset(head, 0, sizeof(head));
minx = inf;
manx = -inf;
cnt = 0;
n = read();
for(int i = 1; i <= n; i++){
int a, b, c;
cin >> a >> b >> c;
add(a - 1, b, c);
minx = min(minx, a - 1);
manx = max(manx, b);
}
for(int i = minx; i <= manx; i++){
add(i, i + 1, 0);
add(i + 1, i, -1);
}
spfa(minx);
cout << dis[manx] << endl;
if(m) printf("
");
}
fclose(stdin);
fclose(stdout);
return 0;
}
/*
做烦了
*/
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
bool f;
int mon;
} vx[B];
vector<int> e[B];
int r, dfn[B], n, m, js, st[B], top, m, low[B], lt[B], sum, in[B], out[B];
int ans, minx[B];
void tarjan(int u){
low[u] = dfn[u] = ++js; st[++top] = u;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]);}
else if(!lt[v]){low[u] = min(low[u], dfn[v]);}
}
if(dfn[u] == low[u]){
lt[u] = sum++;
if(vx[u].f)
minx[sum] = min(minx[sum], vx[x].mon);
while(st[top] != u)
{
if(vx[st[top--]].f)
minx[sum] = min(minx[sum], vx[st[top--]].mon);
lt[st[top]] = sum;
}
lt[st[top--]] = sum;
}
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
memset(minx, inf, sizeof(minx));
n = read();
m = read();
for(int i = 1; i <= m; i++){
int x, mon;
cin >> x >> mon;
vx[x].f = 1, vx[x].cost = mon;
}
r = read();
for(int i = 1; i <= r; i++){
int x, y;
cin >> x >> y;
e[x].push_back(y);
}
for(int i = 1; i <= n; i++)if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++)
for(int j = 0; j < e[i].size(); j++){
int v = e[i][j];
if(lt[i] != lt[v]){
in[lt[v]]++;
}
}
for(int i = 1; i <= sum; i++){
if(!in[i]){
}
cout << ans << endl;
return 0;
}
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
vector<int> e[B];
int dfn[B], n, js, st[B], top, m, low[B], lt[B], sum, in[B], out[B];
int ans;
void tarjan(int u){
low[u] = dfn[u] = ++js; st[++top] = u;
for(int i = 0; i < e[u].size(); i++){
int v = e[u][i];
if(!dfn[v]){ tarjan(v); low[u] = min(low[u], low[v]);}
else if(!lt[v]){low[u] = min(low[u], dfn[v]);}
}
if(dfn[u] == low[u]){
lt[u] = sum++;
while(st[top] != u) lt[st[top--]] = sum;
lt[st[top--]] = sum;
}
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read();
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++){
int x = read();
if(x) e[i].push_back(j);
}
for(int i = 1; i <= n; i++)if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; i++)
for(int j = 0; j < e[i].size(); j++){
int v = e[i][j];
if(lt[i] != lt[v]){
in[lt[v]]++;
}
}
for(int i = 1; i <= sum; i++){
if(!in[i]) ans++;
}
cout << ans << endl;
return 0;
}
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int A = 1e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int nxt, v, w;
} e[B << 1];
int r[B],s[B], vis[B], cnt, dis[B], n, m, head[B], use[B], t, num[B];
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
queue<int> q;
bool spfa(){
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = 0;
use[u] = 0;
for (int i = head[u]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if(dis[v] < dis[u] + w){
dis[v] = dis[u] + w;
use[i]++;
if(use[i] > n - 1) return 0;
if(!vis[v]){
vis[v] = 1;
q.push(v);
}
}
}
}
return 1;
}
int main() {
// freopen(".in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read();
for (int i = 1; i <= m; i++)
{
int x, a, b;
cin >> x >> a >> b;
if(x == 1) add(b, a, 0), add(a, b, 0);
else if(x == 2) add(a, b, 1);
else if(x == 3) add(b, a, 0);
else if(x == 4) add(b, a, 1);
else if(x == 5) add(a, b, 0);
if(x % 2 == 0 && a == b){
cout << -1 << endl;
return 0;
}
}
for(int i = 1; i <= n; i++){
vis[i] = 1;
dis[i] = 1;
use[i] = 1;
q.push(i);
}
if(!spfa())
{
cout << -1 << "
";
return 0;
}
ll ans = 0;
for(int i = 1; i <= n; i++){
ans += dis[i];
}
cout << ans << endl;
fclose(stdin);
fclose(stdout);
return 0;
}
//板子
#include <cmath>
#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
#define eps 1e-12
using namespace std;
const int A = 1e5 + 11;
const int B = 100005;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
struct node{
int v, nxt, w;
} e[B << 1];
int t, head[B], cnt, vis[B], dis[B], n, m, k, flag = 0;
void add(int u, int v, int w){
e[++cnt].nxt = head[u];
e[cnt].v = v;
e[cnt].w = w;
head[u] = cnt;
}
bool spfa(int s){
vis[s] = 1;
for(int i = head[s]; i; i = e[i].nxt)
{
int v = e[i].v, w = e[i].w;
if(dis[v] > dis[s] + w)
{
dis[v] = dis[s] + w;
if(vis[v] || spfa(v)) return 1;
}
}
vis[s] = 0;
return 0;
}
int main() {
freopen("dd.in", "r", stdin);
// freopen(".out", "w", stdout);
n = read(), m = read(), k = read();
int a, b, c;
for (int i = 1; i <= m ; i++)
{
cin >> a >> b >> c;
add(a, b, c);
}
memset(dis, 0x3f, sizeof(dis));
dis[k] = 0;
if(spfa(k))
{
flag = 1;
}
if(head[1] == 0) flag = 1;
if(flag) cout << -1 << endl;
else{
for (int i = 1;i <= n; i++)
if(dis[i] == 1061109567)
cout <<"NoPath" << endl;
else cout<< dis[i] << endl;
}
return 0;
}