图都不用刻意建，按照“最短路”模板题做就行了。。
#include#include #include using namespace std; #define MAXN 30005 #define INF 9999999 #define MAXE 150005 typedef struct Edge { int v, w; int next; }Edge; Edge edge[MAXE]; int dist[MAXN], adj[MAXN]; bool in_s[MAXN]; int size, n, m; void add_edge(int u, int v, int w) { edge[size].v = v; edge[size].w = w; edge[size].next = adj[u]; adj[u] = size++; } void spfa() { int i, u, v, w; int sta[MAXN]; int top = 0; memset(in_s, false, sizeof(in_s)); memset(dist, INF, sizeof(dist)); sta[++top] = 1; dist[1] = 0; in_s[1] = true; while (top) { u = sta[top--]; in_s[u] = false; for (i = adj[u]; i != -1; i = edge[i].next) { v = edge[i].v; w = edge[i].w; if (dist[v] > dist[u] + w) { dist[v] = dist[u] + w; if (!in_s[v]) { in_s[v] = true; sta[++top] = v; } } } } } int main() { int i, a, b, c; cin >> n >> m; for (i = 0; i <= n; i++) adj[i] = -1; size = 0; for (i = 0; i < m; i++) { scanf("%d%d%d",&a,&b,&c); add_edge(a, b, c); } spfa(); printf("%d\n",dist[n]); }