すぬけ君の地下鉄旅行 / Snuke's Subway Trip AtCoder - 2069 (BFS+并查集 ）图论 hqg-ac

すぬけ君の地下鉄旅行 / Snuke’s Subway Trip AtCoder - 2069

题意是从1到$N$，乘多次地铁。每个地铁有一个运营公司。如果公司不同，那么换乘需要1的费用。

解析：

很自然能够想到并查集。

每个并查集维护每个公司的线路，站点等信息

首先读入之后，我们把同公司的线路放入$G$中，

之后，现将每个公司的站点合并到一个并查集里去

之后，新建一个图（类似$bipartite$ $graph$）,左边是站，右边是公司（无向边）

拿第二个样例举例：

之后通过$BFS$求出$DP$数组（表示从1到达N最少的价值数）

注意：

我们发现当要在某公司的某条线上从起点到达终点时，要在图中跑两段路，2 $yen$
不同公司4短路 4 $yen$

于是答案就是$BFS$后的$DP[N]/2$

#include 
using namespace std ;
const int N = 1234567;
vector int,int> > G[N] ;
vector <int> newg[N] ;
queue <int> q ;
int f[N],son[N],id[N],dp[N] ;
bool use[N] ;
int n,m ;
inline void init(int i){f[i]=i;son[i]=0;id[i]=-1;use[i]=false ;
}
int find(int x){return (x==f[x])?x:f[x]=find(f[x]) ; 
}
inline void merge(int x,int y){int X=find(x),Y=find(y) ;if (X==Y) return ;if (son[X]//避免WA?RE? 小技巧 else {f[Y]=X ;if (son[X]==son[Y]) son[X]++ ;}
} 
inline int read(){char c;int f=1 ;while ((c=getchar())<'0' || c>'9') if (c=='-') f=-1 ;int res=c-'0' ;while ((c=getchar())>='0' && c<='9') res=res*10+c-'0' ;return res*f ; 
}
int main(){n=read();m=read() ;for (int i=1;i<=m;i++){int a,b,c ;a=read();b=read();c=read() ;G[c].push_back(make_pair(a,b)) ;}int cnt=n; for (int i=1;i<=N;i++){if (G[i].empty()) continue ; //无该公司 for (int j=0;j//初始 init(G[i][j].first) ;init(G[i][j].second) ;}for (int j=0;jfor (int j=0;jif (!use[G[i][j].first]){use[G[i][j].first]=true ;int X=find(G[i][j].first) ;if (id[X]==-1) id[X]=++cnt ;newg[G[i][j].first].push_back(id[X]) ;//该站点与公司建无向边 newg[id[X]].push_back(G[i][j].first) ;}if (!use[G[i][j].second]){ //同样的工作在second上再做一遍 use[G[i][j].second]=true ;int X=find(G[i][j].second) ;if (id[X]==-1) id[X]=++cnt ;newg[G[i][j].second].push_back(id[X]) ;newg[id[X]].push_back(G[i][j].second) ;}}}q.push(1) ;memset(dp,-1,sizeof(dp)) ;dp[1]=0; //初始在0号节点while(!q.empty()){ //BFS int v=q.front();q.pop() ;for (int i=0;iint to=newg[v][i] ;if (dp[to]==-1){ //还没访问 dp[to]=dp[v]+1 ;q.push(to) ;}}}if (dp[n]==-1) cout<<-1 ;else cout<2 ;
}

当然也有不用并查集的方法（BFS)，

#include using namespace std;const int N = 1234567;int dist[N];
vector < pair <int, int> > g[N];
vector <int> new_g[N], all[N];
int was[N];
int x[N];
int ptr[N];int main() {int n, m;scanf("%d %d", &n, &m);for (int i = 0; i < m; i++) {int foo, bar, qwe;scanf("%d %d %d", &foo, &bar, &qwe);foo--; bar--;g[foo].push_back(make_pair(qwe, bar));g[bar].push_back(make_pair(qwe, foo));all[qwe].push_back(foo);all[qwe].push_back(bar);}for (int i = 0; i < n; i++) {sort(g[i].begin(), g[i].end());ptr[i] = 0;}for (int i = 0; i < n; i++) {was[i] = -1;}int new_n = n;for (int i = 0; i < N; i++) {new_g[i].clear();}for (int color = 0; color < N; color++) {if (all[color].empty()) {continue;}for (int it = 0; it < (int) all[color].size(); it++) {int v = all[color][it];if (was[v] == color) {continue;}int b = 0, e = 1;x[0] = v;was[v] = color;while (b < e) {while (ptr[x[b]] < (int) g[x[b]].size()) {int c = g[x[b]][ptr[x[b]]].first;if (c != color) {break;}int u = g[x[b]][ptr[x[b]]].second;if (was[u] != color) {was[u] = color;x[e] = u;e++;}ptr[x[b]]++;}b++;}for (int i = 0; i < e; i++) {new_g[x[i]].push_back(new_n);new_g[new_n].push_back(x[i]);}new_n++;}}for (int i = 0; i < new_n; i++) {dist[i] = -2;}int b = 0, e = 1;x[0] = 0;dist[0] = 0;while (b < e) {for (int j = 0; j < (int) new_g[x[b]].size(); j++) {int u = new_g[x[b]][j];if (dist[u] == -2) {dist[u] = dist[x[b]] + 1;x[e] = u;e++;}}b++;}printf("%d\n", dist[n - 1] / 2);return 0;
}

还有通过dijkstra解决的方法

#include 
using namespace std ;
const int N = 1e5 +10 ;
const int inf = 0x3f3f3f3f ;
struct st{int p,b,c;};
bool operator < (st a,st b){return a.c>b.c;}
inline int read(){char c;int f=1 ;while ((c=getchar())<'0' || c>'9') if (c=='-') f=-1 ;int res=c-'0' ;while ((c=getchar())>='0' && c<='9') res=res*10+c-'0' ;return res*f ; 
}
map<int ,vector<int> > E[N] ; 
map<int,int > d[N] ; 
vector <int> G[N];
priority_queue  q ;
int n,m;
int main(){n=read();m=read() ;for (int i=1;i<=m;i++){int a,b,c ;a=read();b=read();c=read();a--;b-- ;E[a][c].push_back(b) ;E[b][c].push_back(a) ;G[a].push_back(c) ;G[b].push_back(c) ; }d[0][0]=0;q.push({0,0,0}) ;while(!q.empty()){ //一波Dijkstra st p=q.top();q.pop() ;if (d[p.p][p.b]!=p.c){continue ;}if (d[p.p].find(0)==d[p.p].end() || d[p.p][0]>p.c){d[p.p][0]=p.c ;q.push({p.p,0,p.c}) ;}if (p.b==0){for (int i=0;iint v=G[p.p][i] ;if (d[p.p].find(v)==d[p.p].end() || d[p.p][v]>p.c+1){d[p.p][v]=p.c+1 ;q.push({p.p,v,p.c+1}) ;}}continue ; }for (int i=0;iint v=E[p.p][p.b][i] ;if (d[v].find(p.b)==d[v].end() || d[v][p.b]>p.c){d[v][p.b]=p.c ;q.push({v,p.b,p.c}) ;}}}int ans=inf ;for (map<int,int>::iterator p=d[n-1].begin();p!=d[n-1].end();p++) ans=min(ans,p->second) ;if (ans==inf) printf("-1\n") ;else printf("%d\n",ans) ;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！