题目链接：
本题本来是练习SPFA的。我一看DIscuss能用裸搜。果断敲了一个前向星+DFS，居然超时了。后来发现是Next数组开小了，应该开成两倍边数的大小。
后来我又把前向星改成邻接表，也AC了。。最后写一发SPFA。
前向星+DFS+剪枝：（AC）：
#include#include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3f#define Maxn 5005#define Maxm 40005<<1struct Edge{ int x; int y; int c; int d;};Edge e[Maxm];int first[Maxn];int next[Maxm];//注意不要写成next[Maxn],切记int used[Maxn];int k;int s,t;int n,m;int mma = INF;void dfs(int start,int total_len,int total_k){ //加两个剪支，体力值超过范围或者长度必然不是最优两种情况 if(total_k > k || total_len > mma) { return; } if(start == t) { if(total_k<=k) { mma = mma>total_len ? total_len : mma; } return; } used[start] = 1; for(int i=first[start]; i!=-1; i=next[i]) { if(used[e[i].y] == 0) { dfs(e[i].y,total_len + e[i].d ,total_k + e[i].c); } } used[start] = 0;}int main(){/*#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin);#endif*/ scanf(" %d %d",&n,&m); memset(first,-1,sizeof(first)); memset(next,-1,sizeof(next)); memset(used,0,sizeof(used)); int temp = m; int i = 0; while(temp--) { scanf(" %d %d %d %d",&e[i].x,&e[i].y,&e[i].c,&e[i].d); next[i] = first[e[i].x]; first[e[i].x] = i; i++; e[i].x = e[i-1].y,e[i].y = e[i-1].x,e[i].c = e[i-1].c,e[i].d = e[i-1].d; next[i] = first[e[i].x]; first[e[i].x] = i; i++; } scanf(" %d %d %d",&s,&t,&k); dfs(s,0,0); if(mma == INF) printf("-1\n"); else printf("%d\n",mma);}
邻接表+DFS+剪枝（AC）：
#include#include #include #include #include #include #include #include using namespace std;#define INF 0xffffff#define Maxn 5005#define Maxm 40005<<1struct vertex{ int n; int length; int cost;};vector < vertex > graph[Maxn];int used[Maxn];int k;int s,t;int n,m;int mma = INF;void dfs(int start,int total_len,int total_k){ //加两个剪支，体力值超过范围或者长度必然不是最优两种情况 if(total_k <=k && total_len < mma) { if(start == t) { mma = total_len; } else { used[start] = 1; for(int i=0; i
前向星+SPFA (AC):
声明两个Dist数组，一个代表时间（距离），一个代表体力值，只有两个Dist同时满足条件时，才会更新，也才有机会入队列。
#include#include #include #include #include #include #include #include using namespace std;#define INF 0x3f3f3f3f#define Maxn 5005#define Maxm 40005<<1struct Edge{ int x; int y; int c; int d;};Edge e[Maxm];int first[Maxn];int next[Maxm];int used[Maxn];int distC[Maxn];//体力int distD[Maxn];//时间int k;int s,t;int n,m;void spfa(int s){ queue q; memset(used,0,sizeof(used)); used[s] = 1; q.push(s); while(!q.empty()) { int u = q.front(); q.pop(); used[u] = 0; for(int i=first[u]; i!=-1; i=next[i]) { int v = e[i].y; int c = e[i].c; int d = e[i].d; if(distD[v] - d > distD[u] && distC[u] + c <=k) { distD[v] = distD[u] + d; distC[v] = distC[u] + c; if(used[v] == 0) { used[v] = 1; q.push(v); } } } }}int main(){ /*#ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); #endif*/ scanf(" %d %d",&n,&m); memset(first,-1,sizeof(first)); memset(next,-1,sizeof(next)); memset(used,0,sizeof(used)); memset(distC,0x3f,sizeof(distC)); memset(distD,0x3f,sizeof(distD)); int temp = m; int i = 0; while(temp--) { scanf(" %d %d %d %d",&e[i].x,&e[i].y,&e[i].c,&e[i].d); next[i] = first[e[i].x]; first[e[i].x] = i; i++; e[i].x = e[i-1].y,e[i].y = e[i-1].x,e[i].c = e[i-1].c,e[i].d = e[i-1].d; next[i] = first[e[i].x]; first[e[i].x] = i; i++; } scanf(" %d %d %d",&s,&t,&k); distD[s] = distC[s] = 0; spfa(s); if(distD[t] == INF) printf("-1\n"); else printf("%d\n",distD[t]);}