미 단 b [프로 그래 밍 문제] 배달 2

[프로 그래 밍 문제] 배달 2 시간 제한: 1 초 공간 제한: 32768 K 미 단 배달 일 주문 수 는 1200 만 을 넘 었 고 실시 간 스케줄 링 시스템 은 배후 의 중요 한 기술 기반 으로 복잡 한 알고리즘 과 관련된다.아래 의 제목 은 어떤 장면 의 추상 이다.
n 개의 점 m 조 는 가장자리 에 있 는 그림 에 q 개의 배 송 수요 가 있 습 니 다. 필요 한 설명 형식 은 (s i, t i, l i, r i) 입 니 다. 즉, 점 s 가 필요 합 니 다.i 배달 ti, 시각 li 이후 (l i 포함) si 화물 수령, 시간 ri 이전 (r i 포함) t 전송i, 모든 임 무 는 한 번 만 완성 하면 됩 니 다.그림 의 모든 변 은 변 권 이 있 고 권 가 는 배달 원 이 이 변 을 통 해 소모 하 는 시간 을 대표 한다.시간 0 시 에 배 송 원 한 명 이 시 1 분 에 최대 몇 개의 배 송 임 무 를 완수 할 수 있 는 지 부탁 했다.전체 과정 에서 우 리 는 음식 을 찾 는 시간 과 마지막 으로 사용자 에 게 음식 을 배달 하 는 시간 (실제 장면 에서 이 두 시간 은 생략 할 수 없다) 을 무시 하고 거리 에 걸 리 는 시간 만 고려 했다.또 한 지점 에 머 무 를 수 있다.입력 설명: 첫 번 째 줄, 세 개의 정수 n, m, q (2 ≤ n ≤ 0, 1 ≤ m ≤ 400, 1 ≤ q ≤ 10).다음 m 행, 줄 당 3 개의 정수 ui , v_i , c_i (1 ≤ u i, v i ≤ n, 1 ≤ c i ≤ 20000), ui ~ vi 소모 시간 은 ci 의 방향 이 있다.다음 q 줄, 줄 당 네 개의 정수 si , t_i , l_i , r_i (1 ≤ s i, t i ≤ n, 1 ≤ l i ≤ r i ≤ 10 ^ 6), 배 송 퀘 스 트 를 설명 합 니 다.
출력 설명: 최대 수행 할 수 있 는 작업 의 수 를 나타 내 는 정수 입 니 다.
입력 예: 5, 4, 3, 1, 2, 1, 2, 3, 3, 4, 1, 4, 5, 1, 2, 3, 1, 2, 3, 3, 4, 3, 4, 3, 4, 4.
출력 예: 2
이 문 제 는 먼저 읽 어야 한다. 가장 중요 한 것 은 임 무 는 한 사람 이 완성 하 는 것 이 아니 라 한 길에서 여러 개의 임 무 를 받 을 수 있 는 문 제 를 서 너 번 잘못 읽 었 다 는 것 이다. 마지막 으로 데 이 터 를 봐 야 알 수 있다. 원래 문 제 는 한 사람 이 여러 개의 임 무 를 맡 을 수 있다 는 뜻 이다.

#include 
using namespace std;
int flo[100][100];
int tag[100];
int w[100];

int n,m,q;
int maxs;
int sse=0;
struct node
{
    int x,y,l,r;
}d[100];

void bfs(int s,int t,int v)
{
    //sse++;
    //if(sse>5000000) return ;
    if(t>maxs) maxs=t;
    int x,y,l,r, ts;
    //cout<
    for(int i=0;i//       
    {
        if(w[i]||tag[i]) continue;
        x=d[i].x;
        y=d[i].y;
        l=d[i].l;
        r=d[i].r;
        ts=flo[v][x];
        int k=max(s+ts,l);
        tag[i]=1;
        for(int j=0;jif(d[j].rif(k<=r) bfs(k,t,x);
        tag[i]=0;

    }
    for(int i=0;i//       
    {
        if(w[i]||!tag[i]) continue;
        x=d[i].x;
        y=d[i].y;
        l=d[i].l;
        r=d[i].r;
        ts=flo[v][y];
        //int k=max(s+ts,l);
        //cout<
        if(tag[i]&&s+ts<=r)
        {
            w[i]=1;
            tag[i]=0;
            bfs(s+ts,t+1,y);
            tag[i]=1;
            w[i]=0;
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);

    while(cin>>n>>m>>q)
    {
        memset(flo,10000,sizeof(flo));
        int x,y,z;
        for(int i=1;i<=n;i++) flo[i][i]=0;
        for(int i=0;icin>>x>>y>>z;
            flo[x][y]=min(flo[x][y],z);
            //flo[y][x]=flo[x][y];
        }

        for(int k=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;j<=n;j++)
                {
                    if(flo[i][k]+flo[k][j]//cout<
        for(int i=0;icin>>d[i].x>>d[i].y>>d[i].l>>d[i].r;
        }
        maxs=0;
        bfs(0,0,1);
        cout<