题目已经保证会有一条可到达的路,数据中没有负环。
#include <iostream> #include <stdlib.h> #include <stdio.h> #include <string.h> #include <queue> #include <algorithm> using namespace std; const int maxn = 1010; const int inf = 0x3f3f3f3f; typedef struct Edge { int v, w; Edge(int _v = 0, int _w = 0): v(_v), w(_w) {} }ee; vector<ee> e[maxn]; queue<int> q; void add_edge(int u, int v, int w) { e[u].push_back(Edge(v, w)); } bool vis[maxn]; int cnt[maxn], dis[maxn]; int t, n; bool SPFA(int start) { while(!q.empty()) q.pop(); q.push(start); vis[start] = true; dis[start] = 0,cnt[start] = 1; int u, v; while(!q.empty()) { u = q.front(); q.pop(); vis[u] = false; for(int i = 0; i < e[u].size(); i++) { v = e[u][i].v; if(dis[v] > dis[u] + e[u][i].w) { dis[v] = dis[u] + e[u][i].w; if(!vis[v]) { vis[v] = true; q.push(v); if(++cnt[v] > n) return false; } } } } return true; } int main() { // freopen("2387.in", "r", stdin); while(~scanf("%d%d", &t, &n)) { memset(vis, false, sizeof(vis)); memset(dis, 0x3f, sizeof(dis)); memset(cnt, 0, sizeof(cnt)); int u, v, w; for(int i = 0; i < t; i++) { scanf("%d%d%d", &u, &v, &w); add_edge(u, v, w); add_edge(v, u, w); } if(SPFA(n)) printf("%d\n", dis[1]); } return 0; }