codeforces 592D 题目分析与c++代码实现

Codeforces 592D 题目是一道图论题目，要求你在一张有向图上找到最短路径。

题目描述：给定一张有向图，起点为 $s$，终点为 $t$。要求你求出 $s$ 到 $t$ 的最短路径，并且要求路径上的每条边的权值是 $w_i$，且 $w_i \equiv i \bmod 2$（$i$ 表示边的编号）。

对于此题，我们可以使用Dijkstra算法，该算法是一种贪心算法，适用于解决最短路径问题。

代码实现：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
const int M=2e5+5;
const int INF=0x3f3f3f3f;
int h[N],e[M],ne[M],w[M],idx=0,dis[N];
bool st[N];
int n,m,s,t;
void add(int a,int b,int c)
{
    e[idx]=b,ne[idx]=h[a],w[idx]=c,h[a]=idx++;
}
void dijkstra()
{
    memset(dis,0x3f,sizeof dis);
    priority_queue<pair<int,int> > q;
    q.push({0,s});
    dis[s]=0;
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        int ver=t.second,distance=-t.first;
        if(st[ver]) continue;
        if(ver==t) break;
        st[ver]=true;
        for(int i=h[ver];~i;i=ne[i])
        {
            int j=e[i];
            if(dis[j]>distance+w[i])
            {
                dis[j]=distance+w[i];
                q.push({-dis[j],j});
            }
        }
    }
}
int main()
{
    cin>>n>>m>>s>>t;
    memset(h,-1,sizeof h);
    while(m--)
    {
        int a,b,c;
        cin>>a>>b>>c;