题解-USB迷|专注于互联网分享

题解

蒜头君当大厨
描述

蒜头君苦练厨艺，终于成为了某高档酒店的大厨。

每天上班，蒜头君会被要求做 n 份菜。既然是高档酒店，那么客人们当然是很讲究的，尤其对于上菜的时间有很多要求。客人们的要求被分成下列四种：

菜品 a 的上菜时间必须比菜品 b 的上菜时间早 d 分钟或者更早。

菜品 a 的上菜时间必须比菜品 b 的上菜时间迟 d 分钟或者更迟。

菜品 a 的上菜时间在 d 分钟以后(包含 d 分钟)。

菜品 a 的上菜时间在 d 分钟之前(包含 d 分钟)。

蒜头君的上班时间记为 0 分钟。为了节约时间，在满足客人们要求的情况下，蒜头君希望最后上的一道菜的时间尽可能的早。（每道菜的上菜时间必须不早于蒜头君的上班时间）

输入

第一行输入一个整数 n，表示一共需要上 n 道菜。

第二行输入一个整数 m，表示客人们的要求数量。

接下里 m 行，每行先输入一个整数 op。

如果 op=1，表示描述里的第 1 种要求，后面跟着三个整数 a,b,d。
如果 op=2，表示描述里的第 2 种要求，后面跟着三个整数 a,b,d。
如果 op=3，表示描述里的第 3 种要求，后面跟着两个整数 a,d。
如果 op=4，表示描述里的第 4 种要求，后面跟着两个整数 a,d。

输出

如果蒜头君能满足客人们的要求，输出最后一道菜的上菜时间；否则输出一行 ‘I can’t’。

数据范围和约定

对于所有的数据：1≤n,m≤20000，1≤∣d∣≤10000 ,1≤a,b≤n，a≠b。

样例解释 1

1,2,3 的上菜时间分别为 0,2,12，这样能满足输入客人们的所有要求，并且时间最短。

样例解释 2

t_3t
3

≥t_1t
1

+9, t_1t
1

≥t_3t
3

−1，合并以后得到 t_1t
1

≥t_1t
1

+8，不可能满足客人们的所有要求。

输入样例 1

3
5
2 3 2 10
2 2 1 2
2 3 2 5
1 2 3 7
3 3 9
输出样例 1

12
输入样例 2

3
4
3 1 3
2 3 1 9
2 1 3 -1
1 1 2 5
输出样例 2

I can’t
输入样例 3

17
20
2 6 3 -21
1 8 2 54
3 7 -95
4 11 44
1 5 15 40
3 9 1
3 3 30
3 8 23
2 9 12 -15
4 13 61
2 3 7 31
1 5 10 -15
2 16 1 43
2 12 3 -79
2 14 16 -51
3 6 48
4 7 0
2 10 11 -59
2 12 17 -29
3 4 10
输出样例 3

77
这道题相当于蒜头君的银行卡的升级版，但这道题只是再代码上修改一点就行了。
蒜头君的银行卡：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=10010;
const int maxm=500010;
int n,m;
int dis[maxn];
bool vis[maxn];
int in[maxn];
struct node{int v,w,next;node(){}node(int _v,int _w,int _next){v=_v;w=_w;next=_next;}
}e[maxm];
int head[maxn],len;
void init(){memset(head,-1,sizeof head);len=0;
}
void add(int u,int v,int w){e[len]=node(v,w,head[u]);head[u]=len++;
} 
void add2(int u,int v,int w){add(u,v,w);add(v,u,w);
}
bool spaf(int u){memset(vis,false,sizeof vis);memset(dis,inf,sizeof dis);dis[u]=0;memset(in,0,sizeof in);queue<int> qu;qu.push(u);vis[u]=1;in[u]=1;while(!qu.empty()){u=qu.front();qu.pop();vis[u]=false;for (int j=head[u];~j;j=e[j].next){int v=e[j].v;int w=e[j].w;if (dis[v]>dis[u]+w) {dis[v]=dis[u]+w;if (!vis[v]){qu.push(v);vis[v]=true;in[v]++;if(in[v]>n+1){return false;}}}}}return true;
}
int main(){init();int u,v,w;cin>>n>>m;int op;while(m--){cin>>op;if(op==1){cin>>u>>v>>w;add(u,v,-w);}else if(op==2){cin>>u>>v>>w;add(v,u,w);}else{cin>>u>>v;add(u,v,0);add(v,u,0);}}for(int i=1;i<=n;i++){add(0,i,0);}if(spaf(0)){cout<<"Yes"<<endl; }else{cout<<"No"<<endl;}return 0;
}

AC代码：

#include<bits/stdc++.h>
using namespace std;
const int inf=0x3f3f3f3f;
const int maxn=20010;
const int maxm=500010;
int n,m;
int flag;
int dis[maxn];
bool vis[maxn];
int in[maxn];
struct node{int v,w,next;node(){}node(int _v,int _w,int _next){v=_v;w=_w;next=_next;}
}e[maxm];
int head[maxn],len;
void init(){memset(head,-1,sizeof head);len=0;
}
void add(int u,int v,int w){e[len]=node(v,w,head[u]);head[u]=len++;
} 
void add2(int u,int v,int w){add(u,v,w);add(v,u,w);
}
bool spaf(int u){memset(vis,false,sizeof vis);memset(dis,0x80,sizeof dis);dis[u]=0;memset(in,0,sizeof in);queue<int> qu;qu.push(u);vis[u]=1;in[u]=1;while(!qu.empty()){u=qu.front();qu.pop();vis[u]=false;for (int j=head[u];~j;j=e[j].next){int v=e[j].v;int w=e[j].w;if (dis[v]<dis[u]+w) {dis[v]=dis[u]+w;if (!vis[v]){qu.push(v);vis[v]=true;in[v]++;if(in[v]>n+1){return false;}if(in[v]==n+1){flag=1;return true;}}}}}return true;
}
int main(){init();int u,v,w;cin>>n>>m;int op;while(m--){cin>>op;if(op==1){cin>>u>>v>>w;add(u,v,w);}else if(op==2){cin>>u>>v>>w;add(v,u,w);}else if(op==3){cin>>u>>v;add(0,u,v);}else if(op==4){cin>>u>>v;add(u,0,-v);}}for(int i=1;i<=n;i++){add(0,i,0);}spaf(0);int ans=0;if(flag){cout<<"I can't";return 0;}for(int i=1;i<=n;i++){ans=max(ans,dis[i]);}cout<<ans;return 0;
}

题解