Untitled
unknown
plain_text
5 months ago
6.2 kB
4
Indexable
25 100 7 100 5 6 2000 0 1 600 1000 1 3 700 4000 3 4 200 3000 3 1 400 7000 2 1 300 5000 0 2 200 400 2 0 4 850 400 1 0 4 1050 300 1000 400 3 1 4 -1 200 9000 1 3 100 400 3 1 4 150 30 100 10 20 343235942 9 3 730 511588076 3 6 980 103497954 6 0 390 956612808 0 7 960 588911646 7 5 600 33727076 5 4 260 88489754 4 8 490 527630784 8 1 590 106424790 1 2 220 392166108 2 9 330 538766930 2 1 590 837716110 8 7 200 34689228 2 5 920 794963624 0 5 620 929199098 0 9 600 214614198 6 1 680 214206318 0 1 300 749508458 4 5 870 112136364 4 1 610 372776996 0 3 300 400 2 6 3 345 300 538766930 300 837716110 200 592002819 5 6 180 200 288391792 6 5 890 300 112136364 200 812178983 1 4 660 300 749508458 200 815664058 6 9 880 300 88489754 200 608358041 5 0 190 300 34689228 200 368223732 4 9 310 200 418160571 5 2 430 200 61151304 6 7 190 200 769935373 9 4 190 200 25076024 6 3 810 200 724217617 3 0 720 200 742008262 8 5 540 200 979103957 9 0 600 200 654823290 8 3 460 400 4 2 1 615 200 941874617 7 8 300 200 627206534 8 9 150 400 2 6 9 395 200 661152281 1 8 140 200 104380078 2 7 450 200 4877575 7 0 550 400 8 5 4 130 /* #ifndef _CRT_SECURE_NO_WARNINGS #define _CRT_SECURE_NO_WARNINGS #endif #include <stdio.h> extern void init(int N, int K, int mId[], int sCity[], int eCity[], int mToll[]); extern void add(int mId, int sCity, int eCity, int mToll); extern void remove(int mId); extern int cost(int M, int sCity, int eCity); ///////////////////////////////////////////////////////////////////////// #define MAX_K 2000 #define CMD_INIT 100 #define CMD_ADD 200 #define CMD_REMOVE 300 #define CMD_COST 400 static bool run() { int q; scanf("%d", &q); int n, k, m; int mIdArr[MAX_K], sCityArr[MAX_K], eCityArr[MAX_K], mTollArr[MAX_K]; int mId, sCity, eCity, mToll; int cmd, ans, ret = 0; bool okay = false; for (int i = 0; i < q; ++i) { scanf("%d", &cmd); switch (cmd) { case CMD_INIT: okay = true; scanf("%d %d", &n, &k); for (int j = 0; j < k; ++j) { scanf("%d %d %d %d", &mIdArr[j], &sCityArr[j], &eCityArr[j], &mTollArr[j]); } init(n, k, mIdArr, sCityArr, eCityArr, mTollArr); break; case CMD_ADD: scanf("%d %d %d %d", &mId, &sCity, &eCity, &mToll); add(mId, sCity, eCity, mToll); break; case CMD_REMOVE: scanf("%d", &mId); remove(mId); break; case CMD_COST: scanf("%d %d %d %d", &m, &sCity, &eCity, &ans); ret = cost(m, sCity, eCity); if (ans != ret) okay = false; break; default: okay = false; break; } } return okay; } 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; } */ #include<iostream> #include<vector> #include<queue> #include<unordered_map> #define MAX_INT 1e9 using namespace std ; struct EDGE { int id, to , dis ; bool isDel ; void init(int id , int to , int dis , bool isDel) { this->id = id ; this->to = to ; this ->dis = dis ; this->isDel = isDel ; } }; // danh sach ke vector<EDGE> edgePool[305]; unordered_map<int,EDGE> edgeMap ; struct Node { int city ; int availVou ; int cost ; void init(int city ,int avail , int cost) { this->city = city; this->availVou = avail ; this->cost = cost ; } }; struct cmp { bool operator ()(const Node &a , const Node &b) { if (a.cost !=b.cost) { return a.cost > b.cost ; } return a.availVou < b.availVou ; } }; // priority_queue priority_queue<Node,vector<Node>,cmp> pq ; // thong so ban dau int n ,k ; int minCost[11][305] ; void add(int mId, int sCity, int eCity, int mToll) { EDGE tmpEdge ; tmpEdge.init(mId,eCity,mToll,false); edgePool[sCity].push_back(tmpEdge); edgeMap[mId] = tmpEdge ; return; } void init(int N, int K, int mId[], int sCity[], int eCity[], int mToll[]) { for (int i = 0; i < n; i++) { edgePool[i].clear(); } edgeMap.clear(); n= N ; k = K ; for (int i = 0; i < k; i++) { add(mId[i],sCity[i],eCity[i],mToll[i]); } return; } void remove(int mId) { edgeMap[mId].isDel = true ; } int cost(int M, int sCity, int eCity) { for (int i = 0; i <= n; i++) { for (int j = 0; j <= M; j++) { minCost[j][i] = MAX_INT ; } } // khoi dong pq = priority_queue<Node,vector<Node>,cmp> () ; Node tmpNode ; tmpNode.init(sCity ,M ,0); pq.push(tmpNode); minCost[1][sCity] = 0 ; while (!pq.empty()) { Node curNode = pq.top(); pq.pop(); // neu den dich if (curNode.city == eCity) { return curNode.cost ; } if(curNode.cost > minCost[curNode.availVou][curNode.city]) continue; // quet for (auto i : edgePool[curNode.city]) { if (edgeMap[i.id].isDel == true) continue ; // khong dung ve int nextCost1 = curNode.cost + i.dis ; int nextVou1 = curNode.availVou ; if (nextCost1 < minCost[nextVou1][i.to] ) { minCost[nextVou1][i.to] = nextCost1 ; Node tmpNode2 ; tmpNode2.init(i.to,nextVou1,nextCost1); pq.push(tmpNode2); } // dung ve if (curNode.availVou >=1 ) { int nextCost2 = curNode.cost + i.dis/2 ; int nextVou2 = curNode.availVou - 1; if (nextCost2 < minCost[nextVou2][i.to] ) { minCost[nextVou2][i.to] = nextCost2 ; Node tmpNode3 ; tmpNode3.init(i.to,nextVou2,nextCost2); pq.push(tmpNode3); } } } } return -1; }
Editor is loading...
Leave a Comment