Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
Register

## Re:贡献一组数据。切换灯的时候。如果频率一样。永远都ab点永远不能到达。

Posted by 274856653 at 2019-09-06 17:16:58 on Problem 1158
In Reply To:贡献一组数据。切换灯的时候。如果频率一样。永远都ab点永远不能到达。 Posted by:274856653 at 2019-09-06 17:15:41
```在下水平臭。哈哈。在网上抄了一个题目发现time out。于是改进了一下
#include <stdio.h>
#include<string.h>
#include <iostream>
#include<vector>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>

#define INF 0x3f3f3f3f
#define MAX_M 28000 + 10
#define MAX_N 300 + 10

using namespace std;

int source, target, N, M;
int ric[MAX_N], B[MAX_N], P[MAX_N];
int to[MAX_M], w[MAX_M], pre[MAX_M], pEdge[MAX_N], dis[MAX_N];
int iIndex;
bool inque[MAX_N];
queue<int>q;

void initVar()
{
memset((char *)&ric,    0, sizeof(ric));
memset((char *)&B,      0, sizeof(B));
memset((char *)&P,      0, sizeof(P));
memset((char *)&to,     0, sizeof(to));
memset((char *)&w,      0, sizeof(w));
memset((char *)&pre,    0, sizeof(pre));
memset((char *)&pEdge,  0, sizeof(pEdge));
for(int i = 1; i<=N; i++)
dis[i] = INF;

}

int min(int a, int b)
{
if(a<b)
return a;
else
return b;
}

void inputData()
{

char flag;
for(int i = 1; i<=N; i++)
{
getchar();
scanf("%c %d %d %d", &flag, &ric[i], &B[i], &P[i]);
//			printf("before flag = %c, ric[i] = %d, B[i] = %d, P[i] = %d\n", flag, ric[i], B[i], P[i]);
if('B' == flag )
{
ric[i] = B[i] - ric[i];
}else if('P' == flag)
{
ric[i] = B[i] + P[i]  - ric[i];
}
//			printf("after flag = %d, ric[i] = %d, B[i] = %d, P[i] = %d\n", flag, ric[i], B[i], P[i]);
}
iIndex = 1;
int a, b, weight;
for(int i = 1; i<=M; i++)
{
scanf("%d %d %d", &a, &b, &weight);
//			printf("a = %d, b = %d, weight = %d\n", a, b, weight);

to[iIndex] = b; w[iIndex] = weight; pre[iIndex] = pEdge[a]; pEdge[a] = iIndex++;
to[iIndex] = a; w[iIndex] = weight; pre[iIndex] = pEdge[b]; pEdge[b] = iIndex++;

}
}
void solve()
{
//		printf("source is %d\n", source);
while(q.size()) q.pop();
q.push(source);
dis[source] = 0;
while(q.size())
{
//				printf("q.size() = %d\n", q.size());
int from = q.front();
q.pop();

inque[from] = 0;
//				printf("starthandle from = %d, q.size() = %d\n", from, q.size());
for(int k = pEdge[from]; k; k = pre[k] )
{
//						printf("from = %d, k = %d, to[k] = %d, w[k] = %d\n", from, k, to[k], w[k]);

int wait = 0;
bool bHasPath = true;
while(dis[to[k]] > dis[from] + w[k] + wait )
{

int timea = (dis[from] + ric[from] + wait) % (B[from]+P[from]);
int timeb = (dis[from] + ric[to[k]] + wait) % (B[to[k]]+P[to[k]]);

//printf("timea = %d, B[from] = %d, timeb = %d, B[to[k]] = %d, wait = %d\n", timea, B[from], timeb, B[to[k]], wait );
int aTurnPurple = 0, aTurnBlue = 0;
int bTurnPurple = 0, bTurnBlue = 0;
if((timea < B[from]) != (timeb <B[to[k]]) ) //颜色不一样
{
if(timea<B[from]) //a is blue, will change purple, blue; b is definite purple, blue, plue
{
//printf("test1 \n");
aTurnPurple = B[from] - timea;
bTurnBlue = B[to[k]] + P[to[k]] -timeb;

aTurnBlue = B[from] + P[from] - timea;
bTurnPurple = B[to[k]] + P[to[k]] -timeb + B[to[k]];
//bTurnPurple = B[to[k]] - timeb;

//										printf("aTurnPurple = %d, bTurnBlue = %d, aTurnBlue = %d, bTurnPurple = %d\n",\
aTurnPurple, bTurnBlue, aTurnBlue, bTurnPurple );
if(aTurnPurple == bTurnBlue && aTurnBlue == bTurnPurple )
{
bHasPath = false;
break;
}

}else
{
//init a is purple, b is blue
//printf("test2 \n");
aTurnBlue = B[from] + P[from] - timea;
bTurnPurple = B[to[k]] -timeb;

aTurnPurple =B[from] + P[from] - timea + B[from] ;
bTurnBlue = B[to[k]] + P[to[k]] -timeb;

//										printf("aTurnPurple = %d, bTurnBlue = %d, aTurnBlue = %d, bTurnPurple = %d\n",\
aTurnPurple, bTurnBlue, aTurnBlue, bTurnPurple );
if(aTurnPurple == bTurnBlue && aTurnBlue == bTurnPurple )
{
bHasPath = false;
break;
}

}

wait +=min((timea < B[from])? (B[from] - timea):(B[from] + P[from] - timea), (timeb <B[to[k]])?(B[to[k]] - timeb):(B[to[k]] + P[to[k]] -timeb ) );
//								printf("wait = %d\n", wait);
//
}else
{
break;
}

}
//				printf("final wait = %d, bHasPath = %d \n", wait, bHasPath);
if(!bHasPath)
continue;

if(dis[to[k]] > dis[from] + w[k] + wait )
{
dis[to[k]] = dis[from] + w[k] + wait;
//								printf("update to[k] = %d, dis[to[k]] = %d\n", to[k], dis[to[k]]);
if(!inque[to[k]])
{
q.push(to[k]);
inque[to[k]] = 1;
}
}
}

}
int ans = (dis[target]<INF)? dis[target]:0;
printf("%d\n", ans);

}

int main()
{

int i, j, k;
while(scanf("%d %d %d %d",&source, &target, &N, &M)!=EOF)
{
//			printf("source = %d, target = %d, N = %d, M = %d\n", source, target, N, M);
//		scanf("%d %d %d %d",&source, &target, &N, &M);
initVar();
inputData();
solve();

}
return 0;
}
```

Followed by: