NC16744. 配送
描述
输入描述
第一行三个正整数n, m, k分别表示配送任务数、公交线路数以及城市中包含的关键点点数。
接下来n行，每行一个整数x和一个字符串t，表示需要在恰好t时刻把一个包裹送到下标为x的地点（顾客不会提早到达预定地点，也不能容忍配送员迟到，所以如果配送员早到的话，他需要等到时刻t）。数据不保证任务以t升序的形式给出。
接下来m行，每行三个整数和两个字符串S, T, p, t1，t2，表示S到T有一条价格为p的公交线路，这条线路在每天的t1时刻发车，在t2时刻到达。这些线路都是单向的。
1 <= n <= 10
1 <= m <= 500
1 <= k <= 100
1 <= x <= k
t是Year.Month.Day HH:MM:SS.SSS的形式，其中Year表示年份，Month表示月份，Day表示日期，HH表示小时，MM表示分钟，SS.SSS表示秒数。Day和HH之间是一个空格。数据保证t在2018.07.01 00:00:00.000到2018.07.07 23:59:59.999之间。假设现在的时间是2018.06.30 23:59:59.999，配送员正在1号点上。
数据保证没有两个任务的交货时间是同时的，因此不会发生冲突。
1 <= S, T <= k, S != T
0 < p <= 1,000
数据保证t1、t2在00:00:00.000到23:59:59.999之间，且都是当日出发，当日结束的行程（即t2 > t1）。
对于每个任务，司机需要在严格小于预约时间的时刻到达，在严格大于预约时间的时刻离开。
在这个问题中，不用考虑路上可能的延误。对于行程之间的接续，需要保证后一个行程的起始时间严格大于前一个行程的到达时间。
我们并不在意配送员最后在哪一个地点。
数据保证所有的时间格式合法。Month，Day，HH，MM均为长度为2的字符串，SS.SSS为长度为6的字符串，Year为长度为4的字符串。
输出描述
输出一个整数表示最少需要花费的金钱。
如果不能完成所有任务，请输出-1。
示例1
输入:
2 4 5 1 2018.07.01 10:00:00.000 5 2018.07.02 10:00:00.000 1 2 500 16:00:00.000 17:00:00.000 2 5 500 00:00:00.000 02:00:00.000 2 3 100 20:00:00.000 21:00:00.000 3 5 100 08:00:00.000 09:00:00.000
输出:
700
说明:
配送员有两个任务，他先等在1号地点完成任务1，然后依次通过行程1、3、4到达5号地点完成任务，一共花费700的金钱。Java(javac 1.8) 解法, 执行用时: 192ms, 内存消耗: 19224K, 提交时间: 2018-12-14 07:25:16
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Scanner;
public class Main{
static int dd = 1, md, dq = 0;
static long xzon = Long.MAX_VALUE, dzon = 0;
static String dt = "23:59:59.999", mt, dr = "2018.07.00", mr;
static ArrayList<che> ch[];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt(), m = sc.nextInt(), k = sc.nextInt();
ch = new ArrayList[k + 1];
ArrayList<renwu> li = new ArrayList<>();
for (int i = 0; i < n; i++) {
int a = sc.nextInt();
String b = sc.next(), c = sc.next();
li.add(new renwu(a, b, c));
}
for (int i = 0; i < m; i++) {
int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
String s1 = sc.next(), s2 = sc.next();
if (ch[a] == null)
ch[a] = new ArrayList<>();
ch[a].add(new che(a, b, c, s1, s2));
}
for(int i=1;i<=k;i++) {
if(ch[i]!=null)Collections.sort(ch[i], new Comparator<che>() {
@Override
public int compare(che o1, che o2) {
return o1.money<o2.money?-1:1;
}
});
}
li.sort(new Comparator<renwu>() {
@Override
public int compare(renwu o1, renwu o2) {
int a = o1.time1.compareTo(o2.time1);
if (a != 0)
return a;
return o1.time2.compareTo(o2.time2);
}
});
for (int i = 0; i < n; i++) {
renwu rt = li.get(i);
md = rt.didian;
mr = rt.time1;
mt = rt.time2;
digui();
if (xzon == Long.MAX_VALUE) {
System.out.println(-1);return;
}
dq=0;
dd=md;
dt = rt.time2;
dr = rt.time1;
dzon += xzon;
xzon=Long.MAX_VALUE;
}
System.out.println(dzon);
}
private static void digui() {
if (dd == md) {
if ( dr.compareTo(mr) < 0||(dr.compareTo(mr)==0&&dt.compareTo(mt)<0))
{xzon = Math.min(xzon, dq);}
} else {
if (dr.compareTo(mr) == 0&&ch[dd]!=null) {
String pdt = dt;
int pdd = dd;
int pdq=dq;
for (int i = 0; i < ch[dd].size(); i++) {
che tem = ch[dd].get(i);
if (dt.compareTo(tem.kai) < 0&&dq+tem.money<xzon) {
dt = tem.ting;
dd = tem.end;
dq += tem.money;
digui();
dt = pdt;
dd = pdd;
dq = pdq;
}
}
} else if (dr.compareTo(mr) < 0&&ch[dd]!=null) {
String pdt = dt;
int pdd = dd;
int pdq=dq;
String pdr=dr;
for (int i = 0; i < ch[dd].size(); i++) {
che tem = ch[dd].get(i);
if (dt.compareTo(tem.kai) < 0&&dq+tem.money<xzon) {
dt = tem.ting;
dd = tem.end;
dq += tem.money;
digui();
dt = pdt;
dd = pdd;
dq = pdq;
} else if(dq+tem.money<xzon){
dt = tem.ting;
dd = tem.end;
dq += tem.money;
add();
digui();
dt = pdt;
dd = pdd;
dq = pdq;
dr = pdr;
}
}
}
}
}
private static void add() {
switch (dr) {
case "2018.07.00":
dr = "2018.07.01";
break;
case "2018.07.01":
dr = "2018.07.02";
break;
case "2018.07.02":
dr = "2018.07.03";
break;
case "2018.07.03":
dr = "2018.07.04";
break;
case "2018.07.04":
dr = "2018.07.05";
break;
case "2018.07.05":
dr = "2018.07.06";
break;
case "2018.07.06":
dr = "2018.07.07";
break;
}
}
}
class renwu {
int didian;
String time1, time2;
public renwu(int didian, String time1, String time2) {
this.didian = didian;
this.time1 = time1;
this.time2 = time2;
}
}
class che {
int start;
int end;
int money;
String kai;
String ting;
public che(int start, int end, int money, String kai, String ting) {
this.start = start;
this.end = end;
this.money = money;
this.kai = kai;
this.ting = ting;
}
}
C++14(g++5.4) 解法, 执行用时: 4ms, 内存消耗: 600K, 提交时间: 2018-07-02 21:52:00
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+5,M=1e5+5,inf=2e9;
struct node{
int x,cost,nxt;
string t1,t2;
}a[N],e[N];
bool cmp(node a,node b){
if(a.t1==b.t1)
return a.t2<b.t2;
return a.t1<b.t1;
}
int head[N],tot=0;
bool vis[N],mp[N][N];
int n,m,k,cnt=2e9,ed;
string ed_day="",ed_tim="";
void add_edge(int u,int v,int cost,string t1,string t2)
{
e[tot].x=v,e[tot].cost=cost,e[tot].t1=t1,e[tot].t2=t2;
e[tot].nxt=head[u];
head[u]=tot++;
}
void dfs(int u,int cost,string day,string tim){
if(day>ed_day||(day==ed_day&&tim>=ed_tim)||cost>=cnt)
return;
if(u==ed){
cnt=cost;
return;
}
for(int i=head[u];i!=-1;i=e[i].nxt)
{
int v=e[i].x;
if(vis[v]) continue;
if(e[i].t1>tim)
{
vis[v]=true;
dfs(v,cost+e[i].cost,day,e[i].t2);
vis[v]=false;
}
else{
string nxt_day="";
if(day=="2018.06.30")
nxt_day="2018.07.01";
else
{
nxt_day=day;
nxt_day[9]=day[9]+1;
}
vis[v]=true;
dfs(v,cost+e[i].cost,nxt_day,e[i].t2);
vis[v]=false;
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
memset(head,-1,sizeof(head));
cin>>n>>m>>k;
for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].t1>>a[i].t2;
sort(a+1,a+1+n,cmp);
for(int i=1;i<=m;i++)
{
string t1,t2;
int u,v,x;
cin>>u>>v>>x>>t1>>t2;
add_edge(u,v,x,t1,t2);
}
int res=0;
a[0].x=1,a[0].t1="2018.06.30",a[0].t2="23:59:59.999";
for(int i=1;i<=n;i++)
{
cnt=2e9;
memset(vis,0,sizeof(vis));
ed=a[i].x,ed_day=a[i].t1,ed_tim=a[i].t2;
vis[a[i-1].x]=true;
dfs(a[i-1].x,0,a[i-1].t1,a[i-1].t2);
if(cnt>=2e9)
{
cout<<-1<<'\n';
return 0;
}
res+=cnt;
}
cout<<res<<'\n';
return 0;
}
C++11(clang++ 3.9) 解法, 执行用时: 13ms, 内存消耗: 1132K, 提交时间: 2020-04-03 20:38:20
#include<bits/stdc++.h>
using namespace std;
int n,m,k,res;
struct T
{
int pos;
string tim;
bool operator < (const T &t) const
{
return tim<t.tim;
}
}task[12];
struct edge
{
int v,C;
string t1,t2;
edge(){}
edge(int v,int C,string t1,string t2):v(v),C(C),t1(t1),t2(t2){}
};
vector<edge> G[105];
unordered_map<string,int> mp;
void dfs(int S,T tk,string t1,int val)
{
if(S==tk.pos)
{
res=min(res,val);
return;
}
for(edge e:G[S])
{
if(e.t2>=tk.tim||e.t1<=t1) continue;
if(e.v==tk.pos)
{
res=min(res,val+e.C);
continue;
}
if(mp.count(e.t1)&&mp[e.t1]<=val+e.C)
continue;
mp[e.t1]=val+e.C;
dfs(e.v,tk,e.t2,val+e.C);
}
}
int main()
{
while(cin>>n>>m>>k)
{
string t1,t2;
int u,v,co;
for(int i=0;i<n;i++)
{
cin>>task[i].pos>>t1>>t2;
task[i].tim=t1+" "+t2;
}
sort(task,task+n);
for(int i=0;i<m;i++)
{
cin>>u>>v>>co>>t1>>t2;
for(int j=1;j<=7;j++)
{
string t3="2018.07.0"+to_string(j)+" "+t1;
string t4="2018.07.0"+to_string(j)+" "+t2;
G[u].push_back(edge(v,co,t3,t4));
}
}
int ans=0,S=1;
string ttt="2018.06.30 23:59:59.999";
for(int i=0;i<n;i++)
{
mp.clear();
res=2e9+5;
dfs(S,task[i],ttt,0);
if(res>2e9) break;
ans+=res;
S=task[i].pos;
ttt=task[i].tim;
}
if(res>2e9) cout<<"-1"<<endl;
else cout<<ans<<endl;
}
return 0;
}