提交时间:2024-10-22 21:11:34
运行 ID: 33814
//100,再交一下 #include<bits/stdc++.h> using namespace std; #define int long long #define inx(u) int I=h[(u)],v=edge[I].v,w=edge[I].w;I;I=edge[I].nx,v=edge[I].v,w=edge[I].w const int MAXN=4010,Mod=998244353; int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c<='9'&&c>='0')x=x*10+c-'0',c=getchar();return x*f;} // struct Edge{int v,nx,w;}edge[MAXN<<1];int h[MAXN],CNT;void add_side(int u,int v,int w){edge[++CNT]={v,h[u],w};h[u]=CNT;} struct side{ int u,v,w;char c; }s[MAXN<<1]; int n,m,g[MAXN],f[MAXN]; bool check(char x){ memset(f,0x3f,sizeof(f)); f[1]=0; for(int i=1;i<=m;i++)s[i].w=s[i].c==x?1:-1; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[s[j].v]=min(f[s[j].u]+s[j].w,f[s[j].v]); memcpy(g,f,sizeof(f)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) f[s[j].v]=min(f[s[j].u]+s[j].w,f[s[j].v]); for(int i=1;i<=n;i++)if(f[i]!=g[i])return 0; return 1; } void slv(){ n=read(),m=read(); for(int i=1;i<=m;i++){ int u=read(),v=read(); char c=getchar();while(c!='('&&c!=')')c=getchar(); s[i]={u,v,0,c}; } printf("%s",check('(')^check(')')?"No":"Yes"); } signed main(){ slv(); return 0; }