陕西西安建设厅官方网站,新沂市建设局网站,谷歌搜索引擎,学校建网站次短路
P2829 大逃离 题意#xff1a;给定一个无向图#xff0c;入口1#xff0c;出口n,求第二短路的值 一个节点所直接连接的地方小于k个#xff08;起点和终点除外#xff09;#xff0c;那么他就不敢进去。 n5000#xff0c;m100000 思路#xff1a;次短路…次短路
P2829 大逃离 题意给定一个无向图入口1出口n,求第二短路的值 一个节点所直接连接的地方小于k个起点和终点除外那么他就不敢进去。 n5000m100000 思路次短路为某一条边的长度起点到该边一条端点的最短路终点到另一条边的最短路 spfa跑从起点从终点的最短路之后枚举所有的边连接点的记录可能有重边用vis标记
#includeiostream
#includecstdio
#includequeue
#includecstring
using namespace std;
#define fr(i,z,n) for(int i z;i n; i)
#define fer(i,x) for(int ie.head[x];i;ie.next[i])
const int N 5002, M 100002, INF 1e9 7;
int n, m, k, mindist, secdist INF;//mindist最短路,secdist次短路
int t[N], dist[2][N];//t是每个点的出边数
bool used[N], vis[N];
templatesize_t size
struct Road {int to[size], next[size], head[size], cnt 1;int w[size];void add(int x, int y, int ww) {to[cnt] y;w[cnt] ww;next[cnt] head[x];head[x] cnt;}void clear(int n) {for (int i 0; i n; i) {head[i] 0;}cnt 1;}
};
Road(1000101)e;
void SPFA(int S, int op)//op0是起点的参数,op1是终点的参数
{for (int i 1; i n; i) {dist[op][i] INF, used[i] 0;}queueint Q;Q.push(S);used[S] 1;dist[op][S] 0;while (!Q.empty()){int now Q.front(); Q.pop();used[now] 0;fer(i,now){int v e.to[i];int w e.w[i];if (dist[op][now] w dist[op][v] t[v] k)//筛掉不合法的(即小于k的){dist[op][v] dist[op][now] w;if (!used[v]) { Q.push(v); used[v] 1; }}}}
}
int main() {scanf(%d%d%d, n, m, k);for (int i 1; i m; i) {int u, v, w;scanf(%d%d%d, u, v, w);e.add(u, v, w);e.add(v, u, w);}fr(i, 1, n) { //记录每一个节点的连接点数memset(vis, 0, sizeof(vis));fer(j, i) {int v e.to[j];if (!vis[v]) { //防止重边自环也算t[i];vis[v] 1;}}}t[1] INF; t[n] INF; //起点与终点不包括SPFA(1, 0);SPFA(n, 1);mindist dist[0][n];for (int i 1; i n; i) { //枚举所有边if (t[i] k)continue;fer(j, i) {{int v e.to[j];int len dist[0][i] e.w[j] dist[1][v];if (len mindist t[v] k)secdist min(secdist, len);}}}printf(%d\n, secdist INF ? -1 : secdist);return 0;
}
单源最短路-多源最短路
P5304 [GXOI/GZOI2019] 旅行者(单源最短路-多源最短路) 题意给定一个有向图求给定的k个城市的两两城市间最短路的最小值 n1e5,m5e5,kn 思路两遍dijkstra, 第一次将所有给定点的点加入到队列,(相当于从所有给定点出发到其他点的最短路) 于是需要维护两个东西。1.最短路的距离2到当前点的最短路的起点(相当于染色操作) 第二次建立反图同样将所有给定点的点加入到队列求出其他点到给定点的最短路 同样维护两个东西。1.最短路的距离2最短路对应的终点 遍历每一条边当起点!终点(自环)时更新答案
#includeiostream
#includealgorithm
#includemap
#includeset
#includequeue
#includecstring
#includemath.h
#includemap
#includevector
#includestack
#includearray
#define endl \n
#define ios ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr)
#define ms(x,y) memset(x,y,sizeof x);
#define YES coutYES\n;
#define NO coutNO\n;
#define fr(i,z,n) for(int i z;i n; i)
#define fer(i,x) for(int ie.head[x];i;ie.next[i])
#define fer1(i,x) for(int ie1.head[x];i;ie1.next[i])
#define ufr(i,n,z) for(int i n;i z; i--)
#define int long long
typedef long long ll;
const ll N 2e5 10, inf 1e18;
const ll mod 1e9 7;
using namespace std;
templatesize_t size
struct Road {int to[size], next[size], head[size], cnt 1;ll w[size];void add(int x, int y, ll ww) {to[cnt] y;w[cnt] ww;next[cnt] head[x];head[x] cnt;}void clear(int n) {for (int i 0; i n; i) {head[i] 0;}cnt 1;}
};
Road(500010)e;
Road(500010)e1;
int a[N];
int dis1[N], dis2[N];
int col1[N], col2[N];
bool vis[N];
int n, m, k;
void dijkstra1() {fr(i, 1, n) {dis1[i] inf;vis[i] 0;}priority_queuepairint, int, vectorpairint, int , greaterpairint, int q;fr(i, 1, k) {q.push({ 0,a[i] });dis1[a[i]] 0;col1[a[i]] a[i];}while (!q.empty()) {int x q.top().second;q.pop();if (vis[x]) {continue;}vis[x] 1;fer(i, x) {int v e.to[i];int w e.w[i];if (dis1[x] w dis1[v]) {dis1[v] dis1[x] w;q.push({ dis1[v],v });col1[v] col1[x]; //染色,标记起点}}}
}
void dijkstra2() {fr(i, 1, n) {dis2[i] inf;vis[i] 0;col2[i] 0;}priority_queuepairint, int, vectorpairint, int , greaterpairint, int q;fr(i, 1, k) {q.push({ 0,a[i] });dis2[a[i]] 0;col2[a[i]] a[i];}while (!q.empty()) {int x q.top().second;q.pop();if (vis[x]) {continue;}vis[x] 1;fer1(i, x) {int v e1.to[i];int w e1.w[i];if (dis2[x] w dis2[v]) {dis2[v] dis2[x] w;q.push({ dis2[v],v });col2[v] col2[x]; //染色,标记起点}}}
}
void solve() {cin n m k;e.clear(n);e1.clear(n);vectorarrayint, 3ve;fr(i, 1, n) {col1[i] 0;col2[i] 0;}fr(i, 1, m) {int u, v, w;cin u v w;e.add(u, v, w); //有向图e1.add(v, u, w);ve.push_back({ u,v,w });}fr(i, 1, k) {cin a[i];}dijkstra1();dijkstra2();int ans inf;for (auto it : ve) { //遍历所有的边int u it[0];int v it[1];int w it[2];// cout u v col1[u] col2[v] \n;if ((col1[u]col2[v]) col1[u] ! col2[v]) {// cout YES \n;ans min(ans, dis1[u] dis2[v]w);}}cout ans \n;
}signed main()
{ios;int t 1;cin t;while (t--) {solve();}
}割点联通块
P3469 [POI2008] BLO-Blockade 给定一个无向图(图是联通的)无重边对于每个节点求出去与节点i关联的所有边去掉以后(不去掉节点i本身), 无向图有多少个有序点(x, y)满足x 和y 不连通。 n1e5,m5e5 讨论要删的点是不是割点 1.非割点,则为2*(n-1) 2.割点,导致变成多个联通块不同联通块不可相互到达 假设割后产生2个的联通块大小为a,b,则贡献为2ab2(n-1), 假设产生k联通块2(n-1)2∑(1ik)∑(1jk,j!i)sizei*sizej 会超时∑(1jk,j!i)sizej优化为n-sizei-1 于是变为2∑(1ik)sizei*(n-sizei-1) 转为求联通块大小问题 再dfs的过程中用sum防止重复计算的
#includeiostream
#includestack
#includealgorithm
#includevector
#includequeue
#define int long long
const int N 5e5 10;
using namespace std;
vectorint edges[N];
vectorint edges2[N];
stackintstk;
int dfsn[N], low[N], instk[N], cnt;
int n, m;
int ans[N], Size[N];
int tot;
void tarjan(int p){low[p] dfsn[p] cnt;instk[p] 1;Size[p] 1; int sum 0;stk.push(p); // 进栈for (auto q : edges[p]) {if (!dfsn[q]) { // 未访问过tarjan(q); // 递归地搜索Size[p] Size[q]; //子树的大小 if (low[q] dfsn[p]) { // p为割点满足low[q] dfsn[p]ans[p] Size[q] *(sum); //以p为子树的贡献点sum Size[q];} low[p] min(low[p], low[q]);}else {low[p] min(low[p], dfsn[q]);}}ans[p] (n - sum - 1) * sum;//剩下的点产生的贡献ans[p] n - 1;
}
signed main() {cin n m;for (int i 1; i m; i) {int x, y;cin x y;edges[x].push_back(y);edges[y].push_back(x);}for (int i 1; i n; i)if (!dfsn[i])tarjan(i);for (int i 1; i n; i) {cout 2*ans[i] \n;}
}
