Age of Moyu HDU - 6386 （杭电多校7A）

给出n和点，m条边，每条边有各自的标号，进入第一个标号需要消耗1的费用，此后转换标号需要1费用，在同一个标号上走不需要费用。问你从1到n最少需要多少费用。

最短路变形，把第一个点看成不存在的标号，然后从第一个点开始走，然后就是dijkstra了...当时没好好学dij的优化，当场的时候没加堆优化，乱T....

#include<map>

#include<set>

#include<ctime>

#include<cmath>

#include<stack>

#include<queue>

#include<string>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define lowbit(x) (x & (-x))

typedef unsigned long long int ull;

typedef long long int ll;

const double pi = 4.0*atan(1.0);

const int inf = 0x3f3f3f3f;

const int maxn = ;

const int maxm = ;

const int mod = ;

using namespace std;

int n, m;

int T, tol;

struct Node {

    int v, f, w;

    int next;

    bool operator < (Node a) const {

        return w > a.w;

    }

};

Node node[maxm];

int head[maxn];

bool vis[maxn];

int dis[maxn];

void init() {

    tol = ;

    memset(vis, , sizeof vis);

    memset(dis, inf, sizeof dis);

    memset(head, -, sizeof head);

}

void addnode(int u, int v, int f) {

    node[tol].v = v;

    node[tol].f = f;

    node[tol].next = head[u];

    head[u] = tol++;

}

void dijkstra() {

    dis[] = ;

    priority_queue<Node > q;

    while(!q.empty()) q.pop();

    Node now;

    now.v = ;

    now.f = ;

    now.w = ;

    q.push(now);

    while(!q.empty()) {

        now = q.top();

        q.pop();

        int u = now.v;

        if(vis[u])    continue;

        vis[u] = true;

        dis[u] = now.w;

        for(int i=head[u]; ~i; i=node[i].next) {

            int v = node[i].v;

            if(!vis[v]) {

                Node nex;

                nex.v = v;

                nex.f = node[i].f;

                nex.w = dis[u] + (node[i].f != now.f);

                q.push(nex);

            }

        }

    }

}

int main() {

    while(~scanf("%d%d", &n, &m)) {

        init();

        int u, v, w;

        for(int i=; i<=m; i++) {

            scanf("%d%d%d", &u, &v, &w);

            addnode(u, v, w);

            addnode(v, u, w);

        }

        dijkstra();

        if(dis[n] == inf)    printf("-1\n");

        else    printf("%d\n", dis[n]);

    }

    return ;

}