题意:有n座城市,城市之间有道路,道路需要收费,现在Bob想从城市1去城市n,但是他所拥有的钱是有限制的。现在问Bob能否在有限的钱之内到达n城,若能则输出最短路径。
题解:一开始用vector建图,果断TLE··。可能是从尾部添加邻接点的原因吧。
#include <vector> #include <iostream> using namespace std; #define N 10005 #define INF 99999 struct Edge { int v, len, cost, next; } edge[N]; int vis[101], head[N]; int ans, k, n, r; void dfs ( int u, int len, int money ) { if ( len >= ans ) return; if ( u == n ) { ans = len; return; } for ( int i = head[u]; i ; i = edge[i].next ) { if ( !vis[edge[i].v] && money >= edge[i].cost ) { vis[edge[i].v] = true; dfs ( edge[i].v, len + edge[i].len, money-edge[i].cost ); vis[edge[i].v] = false; } } } int main() { int u, v, l, c; memset(vis,0,sizeof(vis)); memset(edge,0,sizeof(edge)); memset(head,0,sizeof(head)); scanf("%d%d%d",&k,&n,&r); int i = 0; while ( r-- ) { scanf("%d%d%d%d",&u,&v,&l,&c); i++; edge[i].v = v; edge[i].len = l; edge[i].cost = c; edge[i].next = head[u]; head[u] = i; } ans = INF; vis[1] = true; dfs ( 1, 0, k ); if ( ans == INF ) printf("-1\n"); else printf("%d\n",ans); return 0; }
#include <queue> #include <iostream> using namespace std; #define N 10005 struct Edge { int v, len, cost, next; } edge[N]; struct Node { int v, len, cost; friend bool operator<(Node a, Node b) { return a.len > b.len; } } node[N]; int head[N]; int k, n, r; priority_queue<Node> que; /* 优先队列可以保证每次取出距离最小的点 */ int BFS() { Node now, next; now.cost = 0; now.len = 0; now.v = 1; que.push(now); while ( ! que.empty () ) { now = que.top (); que.pop(); if ( now.v == n ) return now.len; for ( int i = head[now.v]; i; i = edge[i].next ) { if ( edge[i].cost + now.cost <= k ) { next.v = edge[i].v; next.len = edge[i].len + now.len; next.cost = edge[i].cost + now.cost; que.push(next); } } } return -1; } int main() { int u, v, l, c; scanf("%d%d%d",&k,&n,&r); int i = 0; memset(head,0,sizeof(head)); while ( r-- ) { scanf("%d%d%d%d",&u,&v,&l,&c); i++; edge[i].v = v; edge[i].len = l; edge[i].cost = c; edge[i].next = head[u]; head[u] = i; } int ans = BFS(); if ( ans == -1 ) printf("-1\n"); else printf("%d\n",ans); return 0; }