本文主要是介绍Codeforces Round 933 (Div. 3)G. Rudolf and Subway 虚点辅佐的dijkstra，用的链式前向星，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Problem - G - Codeforces
推荐视频题解：G_哔哩哔哩_bilibili
思路：
先不管同一个线路上的，就正常建边，这样点距都是1.
然后虚点就是该线路的每个点都连的点。
到虚点的边权是1，表示我们坐这趟线路。
然后这个虚点能去的点的边权都是0.
链式前向星要开3倍的，分别是（都是双向，所以nxt要开6*maxn）
1.车站间的
2.每个车站与虚点相连的
3.每个虚点连的所有车站
参考代码：
const int maxn = 2e5 + 5;//链式前向星 <邻接表>
int tot = 0;//total 下标
int head[maxn*3];//这个邻接表的头的位置
int nxt[maxn * 6];//下一个点的下标
int node[maxn * 6];//每个点的编号
int val[maxn * 6];//边权
inline void add(int a, int b, int t = 1)
{tot++;nxt[tot] = head[a];head[a] = tot;node[tot] = b;val[tot] = t;//a到b的权值
}int b, e;
int ans;
int color[maxn];
int ctot = 0;int tmpdis = 1;
struct dis_node//放堆里面比长度，但是想知道端点
{int dis;int next;bool operator < (const dis_node& a){return dis < a.dis;}dis_node(int d, int n){dis = d; next = n;}
};
class cmp
{
public:bool operator()(dis_node a, dis_node b){return a.dis > b.dis;//}
};
void dijkstr(vector<int>& dij, int ori, int n)
{priority_queue<dis_node, vector<dis_node>, cmp>heap;vector<int>barr(n+2);int cur = ori;while (1){//该次点所有可走的//for (auto next : arr[cur])//{// if (next == cur)continue;// //next就是下一个点（邻接表// if (dij[next] == 0)// dij[next] = dij[cur] + tmpdis;// else// dij[next] = min(dij[next], dij[cur] + tmpdis);// heap.push(dis_node(dij[next], next));//}for (int i = head[cur]; i; i = nxt[i]){if (node[nxt[i]] == cur)continue;if(dij[node[i]] == 0)dij[node[i]] = dij[cur] + val[i];elsedij[node[i]] = min(dij[node[i]], dij[cur] + val[i]);heap.push(dis_node( dij[node[i]], node[i] ));}//该点已使用，已最短，无需再抵达barr[cur] = 1;//最短路中找最短，同时可抵达的while (heap.size()){if (barr[heap.top().next] == 0)break;heap.pop();}if (heap.size() == 0)break;cur = heap.top().next;heap.pop();}
}void solve()
{int n, m;cin >> n >> m;ans = n;memset(color, 0, sizeof(int)*(ctot+1));tot = ctot = 0;memset(head, 0, sizeof(int)* (n + 1) * 2);map<int, int>cpos;for (int i = 0; i < m; i++){int u, v, c;cin >> u >> v >> c;add(u, v,1);add(v, u,1);if (color[cpos[c]] == 0){ctot++;cpos[c] = ctot;color[ctot] = ctot + n;}add(color[cpos[c]], u, 0);add(u, color[cpos[c]], 1);add(color[cpos[c]], v, 0);add(v, color[cpos[c]], 1);}cin >> b >> e;if (b == e){cout << 0 << endl;return;}vector<int>dij(n+m+2);dijkstr(dij,b,n+m+2);cout << dij[e] << endl;
}这篇关于Codeforces Round 933 (Div. 3)G. Rudolf and Subway 虚点辅佐的dijkstra，用的链式前向星的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
