本来想写spfa 加点什么限制什么的可能就过了 写着写着就成裸BFS了 也没优化就水过了
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<stdlib.h> 6 #include<queue> 7 using namespace std; 8 #define N 110 9 #define M 10010 10 #define INF 0xfffffff 11 struct node 12 { 13 int u,v,w,next,len; 14 }ed[M<<1]; 15 struct mode 16 { 17 int u,sum,len; 18 }; 19 int head[N],vis[N],dis[N]; 20 int n,m,t,sp,ans; 21 void init() 22 { 23 t = 0; 24 memset(head,-1,sizeof(head)); 25 } 26 void add(int u,int v,int w,int len) 27 { 28 ed[t].u = u; 29 ed[t].v = v; 30 ed[t].w = w; 31 ed[t].len = len; 32 ed[t].next = head[u]; 33 head[u] = t++; 34 } 35 void spfa() 36 { 37 queue<mode>q; 38 mode ss,st; 39 int i; 40 for(i = 2; i <= n ; i++) 41 dis[i] = INF; 42 ss.u = 1; 43 ss.sum = 0; 44 ss.len = 0; 45 q.push(ss); 46 dis[1] = 0; 47 while(!q.empty()) 48 { 49 ss = q.front(); 50 q.pop(); 51 int u = ss.u; 52 if(ss.len>ans) 53 continue; 54 if(u==n) 55 { 56 ans = ss.len; 57 continue; 58 } 59 for(i = head[u] ; i!=-1 ; i = ed[i].next) 60 { 61 int v = ed[i].v; 62 if(ss.sum+ed[i].w<=sp) 63 { 64 st.len = ss.len+ed[i].len; 65 st.u = v; 66 st.sum = ss.sum+ed[i].w; 67 q.push(st); 68 } 69 } 70 } 71 if(ans!=INF) 72 printf("%d ",ans); 73 else 74 printf("-1 "); 75 } 76 int main() 77 { 78 int i,u,v,len,w; 79 while(scanf("%d",&sp)!=EOF) 80 { 81 init(); 82 ans = INF; 83 scanf("%d%d",&n,&m); 84 for(i = 1; i <= m ;i++) 85 { 86 scanf("%d%d%d%d",&u,&v,&len,&w); 87 add(u,v,w,len); 88 } 89 spfa(); 90 } 91 return 0; 92 }