cf536d——优先队列的运用

喜欢ヅ旅行 2023-08-17 15:47 99阅读 0赞

## 题目 ##

题目： Lunar New Year and a Wander

题目大意：给定一个n个顶点（编号1~n）、m条边的图，求从顶点1出发的字典序最小的路径（途径的边可重复）。

## 思路 ##

使用一个优先队列就足够了。当访问一个节点，我们将与之相连的、未被访问的节点加入队列，每次取优先队列的队首进行访问。即优先队列中存放的是当前所有可到达且未被访问的节点（因为路径可重复）。

时间复杂度：$\\mathcal\{O\}(m \\log n)$

## 代码 ##

priority\_queue版

1 #include<cstdio>
     2 #include<queue>
     3 #include<vector>
     4 using namespace std;
     5 
     6 typedef long long LL;
     7 const int maxn = 100000 + 10;
     8 vector<int>e[maxn];
     9 vector<int>seq;
    10 bool vis[maxn];
    11 int n, m;
    12 priority_queue<int, vector<int>, greater<int>>Q;
    13 
    14 int main()
    15 {
    16     scanf("%d%d", &n, &m);
    17     for (int i = 0; i < m; i++)
    18     {
    19         int u, v;
    20         scanf("%d%d", &u, &v);
    21         e[u].push_back(v);
    22         e[v].push_back(u);
    23     }
    24     vis[1] = true;
    25     Q.push(1);
    26     while (!Q.empty())
    27     {
    28         int now = Q.top(); Q.pop();
    29         seq.push_back(now);
    30         for (int i = 0; i < e[now].size(); i++)
    31         {
    32             if (!vis[e[now][i]])
    33             {
    34                 Q.push(e[now][i]);
    35                 vis[e[now][i]] = true;
    36             }
    37         }
    38     }
    39     for (int i = 0; i < seq.size(); i++)
    40         printf("%d%c", seq[i], i == seq.size() - 1 ? '\n' : ' ');
    41     return 0;
    42 }

set版（set也能排序，且这里节点值不重复）

1 #include<cstdio>
     2 #include<cstring>
     3 #include<set>
     4 #include<vector>
     5 #include<algorithm>
     6 using namespace std;
     7 
     8 typedef long long ll;
     9 const int maxn = 300000 + 10;
    10 int n, m;
    11 vector<int>vec[maxn];
    12 bool visited[maxn];
    13 
    14 int main()
    15 {
    16     scanf("%d%d", &n, &m);
    17     for (int i = 0;i < m; i++)
    18     {
    19         int u, v;
    20         scanf("%d%d", &u, &v);
    21         vec[u].push_back(v);
    22         vec[v].push_back(u);
    23     }
    24     vector<int>ans;
    25     set<int>st;
    26     st.insert(1);
    27     for (int i = 0; i < n; i++)
    28     {
    29         int u, v;
    30         u = *(st.begin());
    31         ans.push_back(u);
    32         visited[u] = true;
    33         st.erase(u);
    34         for (int j = 0; j < vec[u].size(); j++)
    35         {
    36             v = vec[u][j];
    37             if (!visited[v])  st.insert(v);
    38         }
    39     }
    40     int len = ans.size();
    41     for (int i = 0; i < len; i++)  printf("%d%c", ans[i], i == len - 1 ? '\n' : ' ');
    42 
    43     return 0;
    44 }

参考链接：[https://codeforces.com/blog/entry/64928][https_codeforces.com_blog_entry_64928]

转载于:https://www.cnblogs.com/lfri/p/10346275.html

[https_codeforces.com_blog_entry_64928]: https://codeforces.com/blog/entry/64928