Untitled
unknown
plain_text
25 days ago
8.0 kB
7
Indexable
Never
#include<iostream>
#include<vector>
#include<queue>
#include<climits>
#include<cstring>
using namespace std;
#define MAX 9999999
#define internal 0
#define external 1
int calculateTime(int, int);
vector <pair<int, int>>graph[305][35];
int distMatrix[905][905];
int gv_N;
int gv_K;
int res[4][4];
bool isGroupUpdated = false;
int getDistance(int groupId, int src, int dest)
{
int minTime[32];
for (int i = 0; i < 32; i++)
minTime[i] = INT_MAX;
priority_queue<pair<int, int>>pq;
pq.push({ 0, src });
minTime[src] = 0;
while (!pq.empty())
{
pair<int, int> temp = pq.top();
pq.pop();
int dist = temp.first*-1;
int node = temp.second;
if (node == dest)
return dist;
for (int i = 0; i < graph[groupId][node].size(); i++)
{
int newNode = graph[groupId][node][i].second;
int newDist = graph[groupId][node][i].first + dist;
if (newDist < minTime[newNode])
{
minTime[newNode] = newDist;
pq.push({ newDist*-1, newNode });
}
}
}
return -1;
}
void updateIfChange(int groupId, int s, int d)
{
int dist = getDistance(groupId, s, d);
if (dist != -1 && dist != distMatrix[groupId * 3 + s][groupId * 3 + d])
{
isGroupUpdated = true;
distMatrix[groupId * 3 + s][groupId * 3 + d] = dist;
distMatrix[groupId * 3 + d][groupId * 3 + s] = dist;
}
}
bool updateGroup(int groupId)
{
isGroupUpdated = false;
updateIfChange(groupId, 1, 2);
updateIfChange(groupId, 1, 3);
updateIfChange(groupId, 2, 3);
return isGroupUpdated;
}
void updateResult()
{
res[1][2] = calculateTime(1, 2);
res[2][1] = res[1][2];
res[1][3] = calculateTime(1, 3);
res[3][1] = res[1][3];
res[2][3] = calculateTime(2, 3);
res[3][2] = res[2][3];
}
int groupId1, groupId2, nodeId1, nodeId2;
void updateGroupNodeId(int nodeA, int nodeB)
{
groupId1 = nodeA / 100, groupId2 = nodeB / 100;
nodeId1 = nodeA % 100, nodeId2 = nodeB % 100;
}
void init(int N, int K, int nodeA[], int nodeB[], int Time[])
{
gv_N = N;
gv_K = K;
memset(distMatrix, 0, sizeof(distMatrix));
for (int i = 0; i < 305; i++)
{
for (int j = 0; j < 35; j++)
{
graph[i][j].clear();
}
}
for (int i = 0; i < gv_K; i++)
{
updateGroupNodeId(nodeA[i], nodeB[i]);
if (groupId1 == groupId2)
{
graph[groupId1][nodeId1].push_back({ Time[i],nodeId2 });
graph[groupId1][nodeId2].push_back({ Time[i],nodeId1 });
}
else
{
distMatrix[groupId1 * 3 + nodeId1][groupId2 * 3 + nodeId2] = Time[i];
distMatrix[groupId2 * 3 + nodeId2][groupId1 * 3 + nodeId1] = Time[i];
}
}
for (int i = 1; i <= gv_N; i++)
{
updateGroup(i);
}
updateResult();
}
void addLine(int nodeA, int nodeB, int Time)
{
updateGroupNodeId(nodeA, nodeB);
if (groupId1 == groupId2)
{
graph[groupId1][nodeId1].push_back({ Time,nodeId2 });
graph[groupId1][nodeId2].push_back({ Time,nodeId1 });
if (updateGroup(groupId1))
{
updateResult();
}
}
else
{
distMatrix[groupId1 * 3 + nodeId1][groupId2 * 3 + nodeId2] = Time;
distMatrix[groupId2 * 3 + nodeId2][groupId1 * 3 + nodeId1] = Time;
updateResult();
}
}
void remove(int groupId, int nodeA, int nodeB)
{
for (auto itr = graph[groupId][nodeA].begin(); itr != graph[groupId][nodeA].end(); itr++)
{
if ((*itr).second == nodeB)
{
graph[groupId][nodeA].erase(itr);
break;
}
}
}
void removeLine(int nodeA, int nodeB)
{
updateGroupNodeId(nodeA, nodeB);
if (groupId1 == groupId2)
{
remove(groupId1, nodeId1, nodeId2);
remove(groupId1, nodeId2, nodeId1);
if (updateGroup(groupId1))
{
updateResult();
}
}
else
{
distMatrix[groupId1 * 3 + nodeId1][groupId2 * 3 + nodeId2] = 0;
distMatrix[groupId2 * 3 + nodeId2][groupId1 * 3 + nodeId1] = 0;
updateResult();
}
}
int calculateTime(int nodeA, int nodeB)
{
int ans = -1;
priority_queue<pair<int, int>>pq;
int minTime[905];
for (int i = 0; i < 905; i++)
minTime[i] = MAX;
pq.push({ 0,nodeA });
minTime[nodeA] = 0;
while (!pq.empty())
{
int cur_node = pq.top().second;
int cur_time = pq.top().first*(-1);
pq.pop();
if (cur_node == nodeB)
{
ans = cur_time;
return ans;
}
for (int i = 0; i < 905; i++)
{
if (distMatrix[cur_node][i] != 0)
{
int tot_time = cur_time + distMatrix[cur_node][i];
if (tot_time < minTime[i])
{
minTime[i] = tot_time;
pq.push({ -1 * tot_time, i });
}
}
}
}
return ans;
}
int checkTime(int nodeA, int nodeB)
{
return res[nodeA][nodeB];
}
/*
#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
#include <stdio.h>
extern void init(int N, int K, int mNodeA[], int mNodeB[], int mTime[]);
extern void addLine(int mNodeA, int mNodeB, int mTime);
extern void removeLine(int mNodeA, int mNodeB);
extern int checkTime(int mNodeA, int mNodeB);
#define CMD_INIT 0
#define CMD_ADD 1
#define CMD_REMOVE 2
#define CMD_CHECK 3
#define MAX_LINE 30000
static int nodeA[MAX_LINE];
static int nodeB[MAX_LINE];
static int Time[MAX_LINE];
static bool run()
{
int Q, N, K, ans;
scanf("%d", &Q);
bool ok = false;
for (int q = 0; q < Q; q++)
{
int cmd;
scanf("%d", &cmd);
if (cmd == CMD_INIT)
{
scanf("%d %d", &N, &K);
for (int i = 0; i < K; i++) {
scanf("%d %d %d", &nodeA[i], &nodeB[i], &Time[i]);
}
init(N, K, nodeA, nodeB, Time);
ok = true;
}
else if (cmd == CMD_ADD)
{
scanf("%d %d %d", &nodeA[0], &nodeB[0], &Time[0]);
addLine(nodeA[0], nodeB[0], Time[0]);
}
else if (cmd == CMD_REMOVE)
{
scanf("%d %d", &nodeA[0], &nodeB[0]);
removeLine(nodeA[0], nodeB[0]);
}
else if (cmd == CMD_CHECK)
{
scanf("%d %d", &nodeA[0], &nodeB[0]);
int ret = checkTime(nodeA[0], nodeB[0]);
scanf("%d", &ans);
if (ans != ret) {
ok = false;
}
}
else ok = false;
}
return ok;
}
int main()
{
setbuf(stdout, NULL);
freopen("sample_input.txt", "r", stdin);
int T, MARK;
scanf("%d %d", &T, &MARK);
for (int tc = 1; tc <= T; tc++)
{
int score = run() ? MARK : 0;
printf("#%d %d\n", tc, score);
}
return 0;
}
25 100
34
0 4 38
101 111 58
101 112 49
111 113 93
111 102 56
112 103 38
102 113 71
113 103 34
201 222 41
222 202 32
202 225 36
225 203 57
203 215 53
215 211 35
211 201 72
222 225 76
303 323 77
303 322 49
302 322 36
302 330 64
311 330 34
323 301 64
311 301 31
330 301 57
411 402 43
411 413 35
411 403 77
425 402 33
425 401 32
425 413 63
413 423 38
423 403 71
202 401 51
103 301 93
101 1 45
3 203 79
2 302 47
403 3 59
1 201 39
3 2 1 393
3 1 3 278
3 2 3 671
1 103 202 71
3 3 2 504
1 311 323 35
1 113 101 57
3 1 2 393
2 222 225
3 1 3 278
1 222 211 30
2 225 222
3 1 3 277
2 411 413
3 2 1 393
2 222 211
3 1 3 278
2 322 303
3 2 3 504
1 302 303 75
3 2 3 504
1 222 203 83
3 3 1 242
2 111 102
3 2 1 393
2 411 413
3 3 2 504
1 322 311 43
3 2 1 382
1 303 402 84
3 3 2 385
2 330 311
3 1 2 382
*/Leave a Comment