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

题目大意

原题传送门

大意

给定$N(2\leq N\leq 10^5)$个城市及$M(0\leq M\leq 2\times 10^5)$条地铁线路，第$i$条线路连接$p_i$，$q_i$两座城市，由编号为$c_i$的公司运营，若在同一公司之间的地铁线路之间换乘，花费为0，若在不同公司之间的线路换乘，则花费为1，求从城市$1$到城市$N$的最小花费。若无解则输出$-1$.

思路

当我拿到这一道题时，第一反应就是扔给SPFA，建图时边上只保存公司编号，在计算权值时按公司差异计算，具体实现如下：

然后。。。

就没有然后了。。。

一天之后。。。

当我看了某dalao的题解之后。。。

猛然明白了：拆边！

我们以样例为例：

建出的普通图：

将边拆掉后重建的图：

具体方法：我们将边$(p_i,q_i,c_i)$拆成两点$(p_i,c_i)$和$(q_i,c_i)$，在$p_i$、$(p_i,c_i)$，$q_i$、$(q_i,c_i)$，$(p_i,c_i)$、$(q_i,c_i)$之间连边，并将权值分别赋为$1$,$1$,$0$，意思就是在$p_i$上车需要1元，在$p_i$,$q_i$之间坐车消耗0元，在$q_i$下车又需要1元。

意思就是如果你在$u$站下车，坐的是公司$u_a$的车，所以当前你在公司$u_a$的站台上，若你想前往公司$u_b$的站台乘坐他的车，你就必须去站$u$，并付1元；然后你才能前往站台$u_b$。即你在$u$站换乘的顺序是：站台$u_a$→站$u$→站台$u_b$。

接下来就是SPFA的事情了（你用Dijskra也不错）。

实现细节

我们可以使用C++STL标准库容器map来实现对拆开的边取得编号（Hash也是个不错的选择）。

注意在开数组的时候要扩大几倍（你可以用自己的AC率来尝试一下）。

但是，若用上面的方法就会出问题：我们程序得出的答案不对！

原因就是：我们在换乘的时候，是花了2元的，但题目中只需1元。

所以：注意在输出答案时除以二（你也可以用自己的AC率来尝试一下）。

正解代码

这才是你们最喜欢的东西。

#include<cstdio>
#include<map>
#include<queue>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=1e5;
const int INF=0x3f3f3f3f;
struct Edge {int to,cost;Edge(int a,int b){to=a,cost=b;}
};
vector<Edge> G[8*Maxn+5];
void AddEdge(int u,int v,int w) {G[u].push_back(Edge(v,w));G[v].push_back(Edge(u,w));
}int dist[8*Maxn+5];
bool vis[8*Maxn+5];
void SPFA(int s) {memset(dist,0x3f,sizeof dist);memset(vis,false,sizeof vis);queue<int> q;q.push(s);vis[s]=true,dist[s]=0;while(!q.empty()) {int u=q.front();q.pop();vis[u]=false;for(int i=0;i<G[u].size();i++) {int v=G[u][i].to,w=G[u][i].cost;if(dist[v]>dist[u]+w) {dist[v]=dist[u]+w;if(!vis[v]) {vis[v]=true;q.push(v);}}}}
}map<pair<int,int>,int> P;
int cnt;
int Getid(int u,int c) {if(P.find(make_pair(u,c))!=P.end())return P[make_pair(u,c)];return P[make_pair(u,c)]=++cnt;
}int N,M;
int main() {#ifdef LOACLfreopen("in.txt","r",stdin);freopen("out.txt","w",stdout);#endifscanf("%d %d",&N,&M);cnt=N;for(int i=1;i<=M;i++) {int u,v,c;scanf("%d %d %d",&u,&v,&c);int t1=Getid(u,c);int t2=Getid(v,c);AddEdge(t1,t2,0);AddEdge(u,t1,1);AddEdge(v,t2,1);}SPFA(1);if(dist[N]==INF)puts("-1");else printf("%d\n",dist[N]/2);return 0;
}