uva 1599 Ideal Path （两次bfs）

╰半夏微凉° 2024-02-17 22:07 35阅读 0赞

分析：两次bfs，第一次从n到1逆着来，找到每一个点对应的d\[\]值。第二次从1出发，走的每一步要满足d\[u\]==d\[v\]+1，如果满足这个的时，有多个选择，则选择最小的color值走，

一直走到最后即可。

AC代码：

#include<cstdio>
    #include<cstring>
    #include<queue>
    #include<vector>
    #include<algorithm>
    #define INF 2000000000
    using namespace std;
    const int maxn=1e5+10;
    int n,m;
    struct Edges{
    	int to,w;
    	Edges(int to=0,int w=0):to(to),w(w){}
    }; 
    
    vector<Edges>g[maxn];
    int d[maxn];
    int vis[maxn];
    int ans[maxn];
    
    void bfs(int s){
    	memset(d,-1,sizeof(d));
    	queue<int>q;
    	q.push(s);
    	d[s]=0;
    	while(!q.empty()){
    		int u=q.front();
    		q.pop();
    		
    		for(int i=0;i<g[u].size();i++){
    			Edges e = g[u][i];
    			int v=e.to;
    			if(d[v]!=-1)continue;
    			d[v]=d[u]+1; 
    			q.push(v);
    		}
    	}
    }
    
    void bfs2(int s){
    	memset(vis,0,sizeof(vis));
    	memset(ans,0,sizeof(ans));
    	queue<int>q;
    	q.push(s);
    	vis[s]=1;
    	while(!q.empty()){
            int u=q.front();
    		q.pop();
    		
    		if(u==n)return ;
    		int Min=INF;
    		for(int i=0;i<g[u].size();i++){
    			Edges e = g[u][i];
    			if(d[u]==d[e.to]+1){
    				Min=min(Min,e.w);
    			}
    		}
    		
    		int tmp=d[1]-d[u];
    		if(ans[tmp]==0)
    		  ans[tmp]=Min;
    		else ans[tmp]=min(ans[tmp],Min);
    		
    		for(int i=0;i<g[u].size();i++){
    			Edges e = g[u][i];
    			if(!vis[e.to]&&e.w==ans[tmp]&&d[u]==d[e.to]+1){
    				q.push(e.to);
    				vis[e.to]=1;
    			}
    		}
            
    	}
    }
    
    
    int main(){
    	while(scanf("%d%d",&n,&m)==2){
    		for(int i=0;i<m;i++){
    			int from,to,w;
    			scanf("%d%d%d",&from,&to,&w);
    			g[from].push_back(Edges(to,w));
    			g[to].push_back(Edges(from,w));
    		}
    		
    		bfs(n);	
    		bfs2(1);
    		printf("%d\n%d",d[1],ans[0]);
    		for(int i=1;i<d[1]-d[n];i++){
    			printf(" %d",ans[i]);
    		}
    		printf("\n");
    		
    		for(int i=0;i<maxn;i++)g[i].clear();//注意清0 ！！ 
    	}
    	return 0;
    }