brick同学

您知道前向星这个东西么？

稍微加点剪枝的迭代广搜足够了……这题数据太弱

n（

#include<bits/stdc++.h>
using namespace std;
const int maxn=5001;
int dist[maxn],tired[maxn],in[maxn];
struct edge{
int to;
int v;
int t;
};
int k;
vector<edge> e[400001];
queue<int> q;
void init(){
for(int i=0;i<maxn;i++){
dist[i]=1e9;
tired[i]=1e9;
}

}
void spfa(int s){
dist[s]=0;
tired[s]=0;
in[s]=1;
q.push(s);
while(!q.empty()){
int h=q.front();
in[h]=0;
q.pop();
for(int i=0;i<e[h].size();i++){
if(dist[e[h][i].to]>dist[h]+e[h][i].v&&tired[h]+e[h][i].t<=k){
dist[e[h][i].to]=dist[h]+e[h][i].v;
tired[e[h][i].to]=tired[h]+e[h][i].t;
if(!in[e[h][i].to]){
in[e[h][i].to]=1;
q.push(e[h][i].to);
}
/*if(tired[h]+e[h][i].t>k){
continue;
}
else{
tired[e[h][i].to]=tired[h]+e[h][i].t;
if(!in[e[h][i].to]){
in[e[h][i].to]=1;
q.push(e[h][i].to);
}
}*/
/*if(!in[e[h][i].to]){
in[e[h][i].to]=1;
q.push(e[h][i].to);
}*/
}
}
}
}
int n,m;
int main(){
int a,b,c,d;
edge p,p1;
cin>>n>>m;
init();
for(int i=1;i<=m;i++){
cin>>a>>b>>d>>c;
p.to=b;
p.v=c;
p.t=d;
p1.to=a;
p1.v=c;
p1.t=d;
e[a].push_back(p);
e[b].push_back(p1);
}
int st,end;
cin>>st>>end;

cin>>k;
spfa(st);
if(dist[end]==1e9)cout<<"-1";
else
cout<<dist[end];
return 0;
}

###****裸的爆搜可过****
```c++
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 196288 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 196284 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 196288 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 196288 KiB, score = 10
测试数据 #4: Accepted, time = 15 ms, mem = 196284 KiB, score = 10
测试数据 #5: Accepted, time = 15 ms, mem = 196288 KiB, score = 10
测试数据 #6: Accepted, time = 46 ms, mem = 196284 KiB, score = 10
测试数据 #7: Accepted, time = 125 ms, mem = 196284 KiB, score = 10
测试数据 #8: Accepted, time = 171 ms, mem = 196284 KiB, score = 10
测试数据 #9: Accepted, time = 343 ms, mem = 196284 KiB, score = 10
Accepted, time = 715 ms, mem = 196288 KiB, score = 100
代码
#include <cstdio>
#include <cstring>
#include <algorithm>
using std :: min;
const int INF = 0xffffff;
int n,m,MIN = INF,k,start,end;
bool vis[5001];
struct map {
int c,d;
}v[5001][5001];
inline void input() {
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i++)
for (int j = 1;j <= n;j++) v[i][j].c = v[i][j].d = INF;
for (int i = 1;i <= m;i++) {
int x,y;
scanf("%d%d",&x,&y);
scanf("%d%d",&v[x][y].c,&v[x][y].d);
v[y][x] = v[x][y];
}
scanf("%d%d",&start,&end);
scanf("%d",&k);
}
inline void dfs(int now,int sum,int d) {
if (d > MIN || sum > k) return;
if (now == end) {
MIN = min(MIN,d);
return;
}
for (int i = 1;i <= n;i++)
if (!vis[i] && v[now][i].d != INF && v[now][i].c != INF) {
vis[i] = true;
dfs(i,sum+v[now][i].c,d+v[now][i].d);
vis[i] = false;
}
}
inline void work() {
memset(vis,false,sizeof(vis));
vis[start] = true;
dfs(start,0,0);
if (MIN == INF) printf("-1");
else printf("%d",MIN);
}
int main() {
input();
work();
return 0;
}
```

裸spfa
#include<iostream>
#include<cstdio>
#include<queue>
using namespace std;
#define maxn 99999999
struct edge{
int u;
int val;
int w;
edge *link;
};
edge graph[9000];
edge p[90000];
queue<int> q;
int n,m,op,ed;
int num;
int sum;
int d[9000];
int t[9000];
int visit[9000];
void addedge(int v,int u,int x,int val){
edge *k=&p[num];
k->u=u;
k->val=val;
k->w=x;
k->link=graph[v].link;
graph[v].link=k;
num++;
}
void spfa(int s){
visit[s]=1;
d[s]=0;
q.push(s);
while(!q.empty()){
int u=q.front();
q.pop();
visit[u]=0;
for(edge *l=graph[u].link;l!=NULL;l=l->link){
if(t[u]+l->w<=sum){
if(d[l->u]>d[u]+l->val){
d[l->u]=d[u]+l->val;
t[l->u]=t[u]+l->w;
if(visit[l->u]==0){
visit[l->u]=1;
q.push(l->u);
}
}
}
}
}
}
int main(){
int v,u,x,val;
cin>>n>>m;
for(int i=1;i<=n;i++){
graph[i].link=NULL;
d[i]=maxn;
visit[i]=0;
t[i]=0;
}
for(int i=1;i<=m;i++){
scanf("%d %d %d %d",&v,&u,&x,&val);
addedge(v,u,x,val);
addedge(u,v,x,val);
}
cin>>op>>ed;
cin>>sum;
spfa(op);
if(d[ed]!=maxn)
cout<<d[ed]<<endl;
else
cout<<"-1";
return 0;
}

预处理：终点开始spfa 获得每个点到终点的最小所需体力值
起点dfs 可行性剪枝 最优性剪枝
--第一遍没spfa，过了9个点
#include <cstdio>
#include <queue>
#define INF 439643966

struct edge{
int v,c,d;
edge *link;
};

int n,m,START,END,E,ans=INF,vis[5100]={0},top=0;
edge graph[5100]={0};
edge node[81000];

void add(int u,int v,int c,int d){
edge *l=&node[top++];
l->v=v,l->c=c,l->d=d;
l->link=graph[u].link;
graph[u].link=l;
}

void build(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
int u,v,c,d;
scanf("%d%d%d%d",&u,&v,&c,&d);
add(u,v,c,d);
add(v,u,c,d);
}
scanf("%d%d%d",&START,&END,&E);
}

//SPFA
std::queue<int> q;
int inque[5100]={0};
int dist[5100];

void spfa(int u){
for(int i=1;i<=n;i++)
dist[i]=INF;
dist[u]=0;
q.push(u),inque[u]=1;
while(!q.empty()){
int t=q.front();
q.pop(),inque[t]=0;
edge *l=graph[t].link;
while(l){
if(dist[l->v]>dist[t]+l->c){
dist[l->v]=dist[t]+l->c;
if(!inque[l->v]){
q.push(l->v);
inque[l->v]=1;
}
}

l=l->link;
}

}

}

void dfs(int u,int c,int d){
vis[u]=1;
if(c+dist[u]>E)
return;
if(u==END){
ans=ans<d?ans:d;
return;
}
if(d>=ans)
return;
edge *l=graph[u].link;
while(l){
dfs(l->v,c+l->c,d+l->d);
l=l->link;
}
vis[u]=0;
}

int main(){
build();
spfa(END);
dfs(START,0,0);
if(ans==INF)
printf("-1");
else
printf("%d",ans);

return 0;
}

第二组 WA 什么鬼？
求教！

拆点建图spfa+哈希表。由于懒用了map。不过也是100ms In totle

#include <bits/stdc++.h>
using namespace std;

struct p {
    long to, len, next, kil;
}edge[100001];
long head[5005], top = 0;
void push(long i, long j, long kil, long len)
{
    edge[++top].to = j;
    edge[top].len = len;
    edge[top].kil = kil;
    edge[top].next = head[i];
    head[i] = top;
}
long dis[5005];

long n, m, s, t, lif;
#define gr make_pair
#define po pair<long, long>
queue<po > que; // point, life
set<po> exi;

void spfa()
{    
    memset(dis, 127, sizeof dis);
    dis[s] = 0;
    exi.insert(gr(s, lif));
    for (que.push(gr(s, lif)); !que.empty(); ) {
        po k = que.front(); que.pop(); exi.erase(k);
        //cout << k.first << " " << k.second << endl;
        for (int i = head[k.first]; i; i = edge[i].next) {
            int to = edge[i].to, kil = edge[i].kil, len = edge[i].len;
            if (k.second >= kil && dis[to] > dis[k.first] + len) {
                dis[to] = dis[k.first] + len;
                if (!exi.count(gr(to, k.second-kil))) {
                    exi.insert(gr(to, k.second-kil));
                    que.push(gr(to, k.second-kil));
                }
            }
        }
    }
}

int main()
{
    scanf("%ld%ld", &n, &m);
    for (int i = 1; i <= m; i++) {
        long a, b, c, d;
        scanf("%ld%ld%ld%ld", &a, &b, &c, &d);
        push(a, b, c, d);
        push(b, a, c, d);
    }
    cin >> s >> t >> lif;
    spfa();
    if (dis[t] <= 1000000000) 
        cout << dis[t] << endl;
    else
        cout << -1 << endl;
    return 0;
}

终点开始SFPA算出体力最小值
起点开始DFS，可行性剪枝+最优剪枝
#include <cstdio>
#include <queue>
#define INF 999999999

struct edge{
int v,val,e;
edge *link;
};

int n,m,S,K,T,top=0;
edge graph[5050]={0},node[80080];

void addedge(int u,int v,int e,int val){
edge *l=&node[top++];
l->v=v,l->e=e,l->val=val;
l->link=graph[u].link;
graph[u].link=l;
}

void build(){
scanf("%d%d",&n,&m);
int u,v,e,val;
for(int i=1;i<=m;i++){
scanf("%d%d%d%d",&u,&v,&e,&val);
addedge(u,v,e,val);
addedge(v,u,e,val);
}
scanf("%d%d%d",&S,&T,&K);
}
//SPFA:
int en[5050],inque[5050]={0};
std::queue<int> q;

void spfa(int u){
for(int i=1;i<=n;i++)
en[i]=INF;
int t;
edge *l;
en[u]=0;
q.push(u),inque[u]=1;
while(!q.empty()){
t=q.front();
q.pop(),inque[t]=0;
l=graph[t].link;
while(l){

if(en[t]+l->e<en[l->v]){
en[l->v]=en[t]+l->e;
if(!inque[l->v]){
q.push(l->v);
inque[l->v]=1;
}

}
l=l->link;
}
}

}

//DFS:
int ans=INF,vis[50050]={0};

void dfs(int u,int dist,int e){
if(u==T){
ans=ans<dist?ans:dist;
return;
}
edge *l=graph[u].link;
while(l){
if(dist>ans||en[l->v]>e-l->e)
goto q;
if(!vis[l->v]){
vis[l->v]=1;
dfs(l->v,dist+l->val,e-l->e);
vis[l->v]=0;
}
q: l=l->link;
}

}

int main(){
freopen("in.txt","r",stdin);
build();
spfa(T);
if(en[S]>K){
printf("-1");
return 0;
}
dfs(S,0,K);
printf("%d",ans);
return 0;
}

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<map>
#include<vector>
using namespace std;
int a,b;
int k;
int o,p;
int sum=1000000;
int vis[5000];
struct point{
int x,step,layer;
point(int x=0,int step=0,int layer=0):x(x),step(step),layer(layer){}

};
vector<int>qq[4000];
int yu[5000][5000];
int d[5000][5000];
void ans()
{
memset(vis,0,sizeof(vis));
queue<point>q;
point u(o,0,0);
q.push(u);
point end_point(p);
while(!q.empty())
{

point u=q.front();
q.pop();
int x=u.x;
int step=u.step;
int layer=u.layer;
if(x==end_point.x){sum=min(sum,step);}
else {
for(int i=0;i<qq[x].size();i++)
{

if(step+d[x][qq[x][i]]<=sum&&layer+yu[x][qq[x][i]]<=k){q.push(point(qq[x][i],step+d[x][qq[x][i]],layer+yu[x][qq[x][i]]));}

}

}

}

}
int main()
{
cin>>a>>b;
for(int i=0;i<b;i++)
{
int q,w,e,r;
cin>>q>>w>>e>>r;

qq[q].push_back(w);
yu[q][w]=e;
yu[w][q]=e;
d[q][w]=r;
d[w][q]=r;
qq[w].push_back(q);
}
cin>>o>>p;
cin>>k;
ans();
if(sum==1000000)cout<<"-1";
else{cout<<sum;}
return 0;

}

为什么只有七组过

program a1082;
type pp=^re;
re=record
a,b,c:longint;
d:pp;
end;
var
i,j,k,l,s,t,n,m,ii,jj,kk,ll:longint;
pa:array[0..10000]of pp;
aa,ss:array[0..10000]of int64;
dui:array[0..1000000]of longint;

procedure ff(x,y,z,zz:longint);
var
p:pp;
begin
p:=pa[x];
new(pa[x]);
pa[x]^.c:=z;
pa[x]^.b:=zz;
pa[x]^.a:=y;
pa[x]^.d:=p;
end;

procedure spfa(x,y:longint);
var
i,j,kk,ll,l,r:longint; p:pp;
begin
fillchar(aa,sizeof(aa),$7f div 3);
dui[1]:=x; l:=0; r:=1; aa[x]:=0;
while l<=r do
begin
inc(l);
kk:=dui[l];
p:=pa[kk];
while p<>nil do
begin
if (aa[p^.a]>aa[kk]+p^.c)
or((aa[p^.a]=aa[kk]+p^.c)and(ss[p^.a]>ss[kk]+p^.b)) then
begin
aa[p^.a]:=aa[kk]+p^.c;
ss[p^.a]:=ss[kk]+p^.b;
inc(r);
dui[r]:=p^.a;
end;
p:=p^.d;
end;
end;
if aa[y]>k then begin writeln(-1); halt; end else writeln(ss[y]);
end;

begin
readln(n,m);
for i:=1 to m do
begin
readln(ii,jj,kk,ll);
ff(ii,jj,kk,ll);
ff(jj,ii,kk,ll);
end;
readln(s,t);
readln(k);
spfa(s,t);
end.

program aaaaaa;
type pp=record
a,b,c,d:longint;
end;
var
i,j,k,l,n,m,s,t,ii,jj,kk,ll,ans,an:longint;
a:array[0..5000,0..1500]of pp;
b:array[0..5000]of boolean;

procedure dfs(x,y,z:longint);
var
i,j,l,kk:longint;
begin
if x=t then
begin
// writeln(y,' ',z);
if (y<=k)and(z<ans) then
begin
ans:=z;
an:=y;
end;
exit;
end;
if y>k then exit;
if z>ans then exit;
for i:=1 to a[x,0].d do
if b[a[x,i].a]=false then
begin
b[a[x,i].a]:=true;
y:=y+a[x,i].b;
z:=z+a[x,i].c;
dfs(a[x,i].a,y,z);
b[a[x,i].a]:=false;
y:=y-a[x,i].b;
z:=z-a[x,i].c;
end;
end;
begin

readln(n,m);
for i:=1 to m do
begin
readln(ii,jj,kk,ll);
inc(a[ii,0].d);
a[ii,a[ii,0].d].a:=jj;
a[ii,a[ii,0].d].b:=kk;
a[ii,a[ii,0].d].c:=ll;
inc(a[jj,0].d);
a[jj,a[jj,0].d].a:=ii;
a[jj,a[jj,0].d].b:=kk;
a[jj,a[jj,0].d].c:=ll;
end;
readln(s,t);
readln(k);
ans:=maxlongint;
fillchar(b,sizeof(b),false);
b[s]:=true;
dfs(s,0,0);
// writeln(ans);
// writeln(an);
if ans=maxlongint then writeln(-1) else writeln(ans);
end.

编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 1812 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
测试数据 #2: Accepted, time = 15 ms, mem = 1812 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 1816 KiB, score = 10
测试数据 #6: Accepted, time = 15 ms, mem = 1812 KiB, score = 10
测试数据 #7: Accepted, time = 15 ms, mem = 1820 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 1812 KiB, score = 10
测试数据 #9: Accepted, time = 15 ms, mem = 1816 KiB, score = 10
Accepted, time = 60 ms, mem = 1820 KiB, score = 100

双SPFA处理体力MIN，时间MIN，然后最优性剪枝。

下面情况未考虑：
4 4
1 3 5 2
1 2 1 2
2 3 2 2
3 4 2 1
1 4
6
答案是：5
诸位测试一下自己的通过代码。

应该是dfs加剪枝

测试数据 #0: Accepted, time = 62 ms, mem = 98716 KiB, score = 10
测试数据 #1: Accepted, time = 62 ms, mem = 98720 KiB, score = 10
测试数据 #2: Accepted, time = 78 ms, mem = 98716 KiB, score = 10
测试数据 #3: Accepted, time = 78 ms, mem = 98720 KiB, score = 10
测试数据 #4: Accepted, time = 78 ms, mem = 98716 KiB, score = 10
测试数据 #5: Accepted, time = 78 ms, mem = 98720 KiB, score = 10
测试数据 #6: Accepted, time = 78 ms, mem = 98700 KiB, score = 10
测试数据 #7: Accepted, time = 312 ms, mem = 98716 KiB, score = 10
测试数据 #8: Accepted, time = 171 ms, mem = 98716 KiB, score = 10
测试数据 #9: Accepted, time = 733 ms, mem = 98720 KiB, score = 10
这也太惨不忍睹了吧！！！100多行的代码啊！ 写了三个SPFA！

这题我的思路是预处理+枚举:
不妨记dp[i][0][0]是从源点到i时最少体力对应的(体力,时间)花费, dp[i][0][1]是从源点到i时最小时间对应的(体力,时间)花费, dp[i][1][0]是从汇点到i时最小体力对应的(体力,时间)花费, dp[i][1][1]是从汇点到i时最小时间对应的(体力,时间)花费。那么就会出现四种情况:

dp[i][0][0]+dp[i][1][0]: 从源到i的最小体力和从i到汇点的最小体力下的花费

dp[i][0][0]+dp[i][1][1]: 从源到i的最小体力和从i到汇点的最小时间下的花费

dp[i][0][1]+dp[i][1][0]: 从源到i的最小时间和从i到汇点的最小体力下的花费

dp[i][0][1]+dp[i][1][1]: 从源到i的最小时间和从i到汇点的最小时间下的花费

因此, 枚举点i, 即可算出从源到汇的满足体力限制的最小时间。

共同学习
发一个邻接表的代码，请多指教
#include<stdio.h>
#include<queue>
#include<string.h>
#include <malloc.h>
#define MAXN 5001
#define INF 0x3f3f3f3f
using namespace std;
struct Edge;
struct Node
{
Edge *next;
bool used;
int idx;
}V[MAXN];
struct Edge
{
Edge *next;
Node *to;
int tl,len;
};
int dis[MAXN],T[MAXN],n,m,s,t,k;
void addEdge(struct Node *A,struct Node *B,int tl,int len)
{
struct Edge t = (struct Edge)malloc(sizeof(struct Edge));
t->next = A->next;
t->to = B;
t->tl = tl;
t->len = len;
A->next = t;

}
void spfa(int x)
{
memset(dis,0x3f,sizeof(dis));
queue<Node*>Q;
V[x].used=true;
dis[x]=0;
Q.push(&V[x]);
while(!Q.empty())
{
Node* tmp=Q.front();
Q.pop();
for(struct Edge *e=tmp->next;e;e=e->next)
{
if(dis[tmp->idx]+e->len<dis[e->to->idx]&&T[tmp->idx]+e->tl<=k)
{
dis[e->to->idx]=dis[tmp->idx]+e->len,
T[e->to->idx]=T[tmp->idx]+e->tl;
if(!e->to->used)
{
Q.push(e->to),
e->to->used=true;
}

}
}
tmp->used=false;
}
if(dis[t] == INF)
{
printf("-1\n");

}else
{
printf("%d\n",dis[t]);
}

return;
}
int main()
{
int i;
scanf("%d%d",&n,&m);
for(i=1;i<=n;++i)V[i].idx=i;
for(i=1;i<=m;++i)
{
int x,y,c,d;
scanf("%d%d%d%d",&x,&y,&c,&d);
addEdge(&V[x],&V[y],c,d);
addEdge(&V[y],&V[x],c,d);
}
scanf("%d%d%d",&s,&t,&k);
spfa(s);
}