CF1106D 题解

暑期学校军训第一天模拟赛的题，相对而言比较简单

题意：

题意其实很简单，就是有一个无向图，需要你从\(1\)号节点出发，然后一次遍历所有的点，输出其中字典序最小的遍历

思路

说说思路吧，这题既然要遍历图上所有点，那首先就会想到 \(\texttt{BFS}\) 或 \(\texttt{DFS}\)，可本题还要求要字典序小，这两种方法要把所有情况都遍历一遍才能求出最值，这样显然会 \(\texttt{TLE}\)。那我们再想，这题要求字典序最小的遍历方法，那我们就利就用贪心思想，每次选编号最小的节点去走，这样结果肯定是最优的。

然后这道题就很简单了，一个 \(\texttt{DFS}\) 用优先队列维护一下就做完了~

这里还有一个知识点是链式前向星，就是存图加边的~~一个算是小模板的小小小函数~~

void add(int u,int v){
	tot++;
    a[tot].next=head[u];
    a[tot].to=v ;
    head[u]=tot;
}

~~这个 \(\texttt{DFS}\) 其实我感觉和 \(\texttt{SPFA}\) 里面的代码很像~~，不知道为什么

~~不信给你们看看~~

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
const int INF=0x3f3f3f3f;
struct node{
    int e,w;
};
int n,m,x,y,z;
int dis[N],vis[N];
vector<node> a[N];
queue<int> q;
void spfa(){
    q.push(1);
    vis[1]=1;
    memset(dis,INF,sizeof(dis));
    dis[1]=0;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        vis[u]=0;
        for(int i=0;i<a[u].size();i++){
            int e=a[u][i].e;
            int w=a[u][i].w;
            if(dis[e]>dis[u]+w){
                dis[e]=dis[u]+w;
                if(vis[e]==0){
                    vis[e]=1;
                    q.push(e);
                }
            }
        }
    }
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        cin>>x>>y>>z;
        a[x].push_back({y,z});
        a[y].push_back({x,z});
    }
    spfa();
    cout<<dis[n];
    return 0;
}
//给定M条边，N个点的带权无向图。求1到N的最短路。

~~你看是不是很像~~

好了，还是看看这道题的代码吧

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+100;
int n,m;
struct edge{
    int to,next;
}a[N<<1];
priority_queue<int,vector<int>,greater<int> >q;
int head[N],vis[N],tot;
void add(int u,int v){
	tot++;
    a[tot].next=head[u];
    a[tot].to=v ;
    head[u]=tot;
}
void dfs(){
    q.push(1);
    vis[1]=1;
    while(!q.empty()){
        int u=q.top();
        q.pop() ;
        printf("%d ",u);
        for(int i=head[u];i;i=a[i].next){
            int v=a[i].to;
            if(!vis[v]){
            	vis[v]=1;
            	q.push(v);
			}
        }
    }
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
    	int x,y;
    	scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs();
    return 0 ;
}

总而言之，这道题就是图的遍历，~~我觉得这道题甚至都不可以放在绿题里面，黄题差不多了~~