专栏文章

7.11

bbokaro_kyoku_mania
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miox976w
此快照首次捕获于
2025/12/03 02:38
3 个月前
此快照最后确认于
2025/12/03 02:38
3 个月前
查看原文
P2865:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
}
const int N=1e5+50,M=5e5+50;
int n,m,s;
int head[N],nxt[M],to[M],w[M],tot;
void add(int x,int y,int val){
	to[tot]=y;
	nxt[tot]=head[x];
	w[tot]=val; 
	head[x]=tot++;
}
int d[2][N];
int vis[N];
priority_queue<pair<int,int> >q;
void spfa(int x){
	memset(d,0x3f,sizeof(d));
	d[0][s]=0;
	q.push(make_pair(0,s)); 
	while(!q.empty()){
		int x=q.top().second;
		q.pop();
		for(int i=head[x];~i;i=nxt[i]){
			if(d[0][to[i]]==d[0][x]+w[i]);
			else if(d[0][to[i]]>d[0][x]+w[i]){
				d[1][to[i]]=d[0][to[i]];
				d[0][to[i]]=d[0][x]+w[i];
				q.push(make_pair(-d[0][to[i]],to[i]));
			}
			else if(d[1][to[i]]>d[0][x]+w[i]){
				d[1][to[i]]=d[0][x]+w[i];
				q.push(make_pair(-d[1][to[i]],to[i]));
			}
			if(d[1][to[i]]>d[1][x]+w[i]){
				d[1][to[i]]=d[1][x]+w[i];
				q.push(make_pair(-d[1][to[i]],to[i]));
			}
		}
	}
}
int x,y,r;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(head,-1,sizeof(head));
	read(n);
	read(m);
	s=1;
	for(int i=1;i<=m;i++){
		read(x);
		read(y);
		read(r);
		add(x,y,r);
		add(y,x,r);
	}
	spfa(s);
	write(d[1][n]);
	putchar('\n');
	
	
	
	
	
	return 0; 
}
dijkstra:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
template<typename T>inline void read(T&x){
	x=0;
	char c;
	int sign=1;
	do{
		c=getchar();
		if(c=='-'){
			sign=-1;
		}
	}while(!isdigit(c));
	do{
		x=x*10+c-'0';
		c=getchar();
	}while(isdigit(c));
	x*=sign;
}
inline void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>9)write(x/10);
	putchar(x%10+'0');
	putchar(' ');
}
const int N=1e5+50,M=5e5+50;
int n,m,s;
int head[N],nxt[M],to[M],w[M],tot;
void add(int x,int y,int val){
	to[tot]=y;
	nxt[tot]=head[x];
	w[tot]=val; 
	head[x]=tot++;
}
int d[N];
int vis[N];
priority_queue<pair<int,int> >q;
void dij(int x){
	for(int i=0;i<=n;i++){
		d[i]=INT_MAX;
	}
	d[s]=0;
	q.push(make_pair(-d[s],s)); 
	for(int t=1;t<n;t++){
		while(vis[q.top().second]){
			q.pop();
		}
		x=q.top().second;
		q.pop();
		vis[x]=1;
		for(int i=head[x];~i;i=nxt[i]){
			if(d[to[i]]>d[x]+w[i]){
				d[to[i]]=d[x]+w[i];
				q.push(make_pair(-d[to[i]],to[i]));
			}
		}
	}
}
int x,y,r;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	memset(head,-1,sizeof(head));
	read(n);
	read(m);
	read(s);
	for(int i=1;i<=m;i++){
		read(x);
		read(y);
		read(r);
		add(x,y,r);
	}
	dij(s);
	for(int i=1;i<=n;i++){
		write(d[i]);	
	}
	
	
	
	
	
	
	return 0; 
}
UVA247:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1010;
int g[N][N];
map<string,int>H;
string ans[N];
int b[N];
int n,m,cnt,s=0;
string x,y;
signed main(){
    while(scanf("%d%d",&n,&m)){
        if(n==0&&m==0){
        	break;
		}
        memset(b,0,sizeof(b));
        memset(g,0,sizeof(g));
        H.clear();
        cnt=0;
        for(int i=1;i<=m;i++){
            cin>>x>>y;
            if(H[x]==0){
            	cnt++;
				H[x]=cnt;
				ans[cnt]=x;
			}
            if(H[y]==0){
            	cnt++;
				H[y]=cnt;
				ans[cnt]=y;
			}
            g[H[x]][H[y]]=1;
        }
        for(int k=1;k<=n;k++){
        	for(int i=1;i<=n;i++){
        		for(int j=1;j<=n;j++){
                	g[i][j]|=g[i][k]&&g[k][j];
				}
			}    
		}
        printf("Calling circles for data set %d:\n",++s);
        queue<string> q;
        for(int i=1;i<=n;i++){
            if(b[i]){
            	continue;
			}
            q.push(ans[i]);
            for(int j=i+1;j<=n;j++){
            	if(g[i][j]&&g[j][i]){
                	q.push(ans[j]),b[j]=1;
				}
			}
            while(q.size()!=1){
                cout<<q.front()<<", ";
                q.pop();
            }
            cout<<q.front()<<endl;
            q.pop();
        }
    }
    
    
    
    
    return 0;
}
UVA658:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1<<20,M=105;
int n,m,ti[M],b1[M],b2[M],f1[M],f2[M],dis[N];
bool vis[N];
struct node{
	int p,v;
	bool operator<(const node&k)const{return v>k.v;}
};
void dij(){
	priority_queue<node>q;
	int s=(1<<n)-1;
	q.push({s,0});dis[s]=0;
	while(!q.empty()){
		int t=q.top().p;q.pop();
		if(vis[t])continue;
		vis[t]=1;
		for(int i=1;i<=m;i++){
			int g=t;
			if((g&b1[i])!=b1[i])continue;
			if((g&b2[i])!=0)continue;
			g^=(g&f1[i]);
			g|=f2[i];
			if(dis[g]<=dis[t]+ti[i])continue;
			dis[g]=dis[t]+ti[i];
			q.push({g,dis[g]});
		}
	}
}
int cnt;
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	while(cin>>n>>m&&n&&m){
		memset(dis,0x3f,sizeof dis);
		memset(vis,0,sizeof vis);
		for(int i=1;i<=m;i++){
			cin>>ti[i];
			char c;
			b1[i]=b2[i]=f1[i]=f2[i]=0;
			for(int j=0;j<n;j++){
				cin>>c;
				if(c=='+')b1[i]|=(1<<j);
				if(c=='-')b2[i]|=(1<<j);
			}
			for(int j=0;j<n;j++){
				cin>>c;
				if(c=='+')f2[i]|=(1<<j);
				if(c=='-')f1[i]|=(1<<j);
			}
		}
		dij();
		cnt++;
		cout<<"Product "<<cnt<<'\n';
		if(dis[0]==0x3f3f3f3f3f3f3f3f){
			cout<<"Bugs cannot be fixed.\n";
		}
		else{
			cout<<"Fastest sequence takes "<<dis[0]<<" seconds.\n";
		}
		cout<<'\n';
	}
	
	
	
	
	return 0;
}
UVA10048:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=909;
int n,m,s,d[N][N],vis[N];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	for(int Z=1;;Z++){
		memset(d,0x3f,sizeof(d));
		cin>>n>>m>>s;
		if(n==0&&m==0&&s==0)break;
		if(Z!=1)cout<<"\n";
		cout<<"Case #"<<Z<<"\n";
		for(int i=1;i<=m;i++){
			int x,y,z;
			cin>>x>>y>>z;
			d[x][y]=min(d[x][y],z);
			d[y][x]=min(d[y][x],z);
		}
		for(int i=1;i<=n;i++){
			d[i][i]=0;
		}
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					d[i][j]=min(d[i][j],max(d[i][k],d[k][j]));
				}
			}
		}
		while(s--){
			int x,y;
			cin>>x>>y;
			if(d[x][y]==0x3f3f3f3f3f3f3f3f){
				cout<<"no path\n";
			}
			else cout<<d[x][y]<<"\n";
		}
	}
	
	
	
	
	
	
	
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...