题解 | I Wanna Go Home

dfs直接求解，注意处理一下超时就行，时间好像有点慢，243ms运行完

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

struct Edge {
    int to;
    int time;
    Edge(int to, int time): to(to), time(time) {}
};
vector<Edge> graph[601];
int nationality[601];
int visited[601] = {0};
int n, m;
int res;

void dfs(int cur, int time, int change) {
    //到达终点
    if (cur == 2 && change <= 1) {
        res = min(res, time);
        return ;
    }
    //非法
    if (change > 1)
        return ;
    if(time >res)
        return ;
        
    for (auto x : graph[cur]) {
        if (!visited[x.to]) {
            visited[x.to] = 1;
            nationality[cur] == nationality[x.to] ? dfs(x.to, time + x.time,
                    change) : dfs(x.to, time + x.time, change + 1);
            visited[x.to] = 0;
        }
    }
}

int main() {
    while (cin >> n) {
        if (n == 0) break;
        cin >> m;
        for (int i = 0; i < m; i++) {
            int x, y, t;
            cin >> x >> y >> t;
            graph[x].emplace_back(y, t);
            graph[y].emplace_back(x, t);
        }
        for (int i = 1; i <= n; i++) {
            cin >> nationality[i];
            visited[i] = 0;
        }

        visited[1] = 1;
        res = INT_MAX;
        dfs(1, 0, 0);
        if (res != INT_MAX)
            cout << res << endl;
        else
            cout << "-1" << endl;
        //清理脏数据
        for (int i = 1; i <= n; i++)
            graph[i].clear();
    }
}