3 条题解
-
1赵青海 (huhe) LV 7 SU @ 2023-7-24 21:04:24
/***************************************** 备注: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 2e6 + 10; const int INF = 0x3f3f3f3f; LL head[N] , to[N],w[N],ne[N],idx=0; LL vis[N] , dis[N] ,num[N]; inline void add(int x,int y , int z) { to[++idx] = y; w[idx] = z; ne[idx] = head[x]; head[x] = idx; } LL n , k; LL spfa() { memset(dis,-0x3f, sizeof dis); stack<int> p; dis[n+1] = 0; vis[n+1] = 1; num[n+1] = 1; p.push(n+1); while( !p.empty()) { int t = p.top(); p.pop(); vis[t] = 0; for(int i = head[t] ; i ; i = ne[i]) { int u = to[i]; if(dis[u] < dis[t] + w[i]) { dis[u] = dis[t] + w[i]; if(!vis[u]) { p.push(u); vis[u] = 1; if(++num[u] >= n) return -1; } } } } LL sum = 0; for(int i = 1 ; i <= n+1 ; i++) sum += dis[i]; return sum; } int main() { cin >> n >> k; for(int i = 0 ; i < k ; i++) { int z,x,y; scanf("%d%d%d",&z,&x,&y); if(z == 1) add (x,y,0),add (y,x,0); else if ( z == 2) add(x,y,1); else if( z == 3) add(y,x,0); else if(z == 4) add(y,x,1); else if(z ==5) add(x,y,0); } for(int i = 1 ; i <= n ; i++) add(n+1,i,1); cout << spfa() << endl; return 0; }
-
12023-7-24 20:10:39@
#include <bits/stdc++.h> using namespace std; #define int long long //不开long long见祖宗 const int N=1e6+10; int n,m,head[N],ne[N],w[N],to[N],id,dis[N],vis[N],cnt[N]; inline void add(int x,int y,int z){ to[++id]=y,w[id]=z,ne[id]=head[x],head[x]=id; } int spfa(){ memset(dis,-0x3f,sizeof(dis)); dis[n+1]=0,vis[n+1]=1,cnt[n+1]=1; stack<int> q; q.push(n+1); while(!q.empty()){ int t=q.top(); q.pop(); vis[t]=0; for(int i=head[t];i;i=ne[i]){ int v=to[i]; if(dis[v]<dis[t]+w[i]){ dis[v]=dis[t]+w[i]; if(!vis[v]){ q.push(v),vis[v]=1; if(++cnt[v]>=n) return -1; } } } } int sum=0; for(int i=1;i<=n+1;i++){ sum+=dis[i]; } return sum; } signed main(){ cin>>n>>m; for(int i=0,x,y,z;i<m;i++){ cin>>z>>x>>y; if(z==1){ add(x,y,0),add(y,x,0); }else if(z==2){ add(x,y,1); }else if(z==3){ add(y,x,0); }else if(z==4){ add(y,x,1); }else if(z==5){ add(x,y,0); } } for(int i=1;i<=n;i++) add(n+1,i,1); cout<<spfa(); }
-
02021-11-27 16:14:16@
/***************************************** 备注: ******************************************/ #include <queue> #include <math.h> #include <stack> #include <stdio.h> #include <iostream> #include <vector> #include <iomanip> #include <string.h> #include <algorithm> using namespace std; #define LL long long const int N = 2e6 + 10; const int INF = 0x3f3f3f3f; LL head[N] , to[N],w[N],ne[N],idx=0; LL vis[N] , dis[N] ,num[N]; inline void add(int x,int y , int z) { to[++idx] = y; w[idx] = z; ne[idx] = head[x]; head[x] = idx; } LL n , k; LL spfa() { memset(dis,-0x3f, sizeof dis); stack<int> p; dis[n+1] = 0; vis[n+1] = 1; num[n+1] = 1; p.push(n+1); while( !p.empty()) { int t = p.top(); p.pop(); vis[t] = 0; for(int i = head[t] ; i ; i = ne[i]) { int u = to[i]; if(dis[u] < dis[t] + w[i]) { dis[u] = dis[t] + w[i]; if(!vis[u]) { p.push(u); vis[u] = 1; if(++num[u] >= n) return -1; } } } } LL sum = 0; for(int i = 1 ; i <= n ; i++) sum += dis[i]; return sum; } int main() { cin >> n >> k; for(int i = 0 ; i < k ; i++) { int z,x,y; scanf("%d%d%d",&z,&x,&y); if(z == 1) add (x,y,0),add (y,x,0); else if ( z == 2) add(x,y,1); else if( z == 3) add(y,x,0); else if(z == 4) add(y,x,1); else if(z ==5) add(x,y,0); } for(int i = 1 ; i <= n ; i++) add(n+1,i,1); cout << spfa() << endl; return 0; }
- 1
信息
- ID
- 422
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 7
- 标签
- 递交数
- 163
- 已通过
- 42
- 上传者