| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 105707 | Pro_ktmr | 한자 끝말잇기 (JOI14_kanji) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stdio.h>
#include <math.h>
#include <time.h>
#include <string>
#include <tuple>
#include <vector>
#include <map>
#include <unordered_map>
#include <list>
#include <set>
#include <stack>
#include <queue>
#include <cstdlib>
#include <algorithm>
#include <random>
#include <cassert>
using namespace std;
#define LL long long
#define MP(a, b) make_pair(a, b)
#define POWER9 1000000000
#define MOD POWER9+7
#undef INT_MIN
#undef INT_MAX
#define INT_MIN -2147483647
#define INT_MAX 2147483647
#define LL_MIN (LL)-9223372036854775807
#define LL_MAX (LL)9223372036854775807
#define PI 3.14159265359
#include "kanji.h"
void Anna(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[]){
vector<pair<int,LL> > ko[300],oya[300];
for(int i=0; i<M; i++){
ko[A[i]].push_back(MP(B[i],C[i]));
oya[B[i]].push_back(MP(A[i],C[i]));
}
vector<pair<int,int> > u;
for(int i=0; i<K; i++){
u.push_back(MP(A[U[i]],B[U[i]]));
}
for(int q=0; q<Q; q++){
LL cost[300];
for(int i=0; i<N; i++) cost[i] = LL_MAX;
cost[S[q]] = 0;
priority_queue<pair<LL,int> > que;
que.push(MP(0,S[q]));
while(!que.empty()){
int now = que.top().second;
LL c = -que.top().first;
que.pop();
for(int i=0; i<ko[now].size(); i++){
int next = ko[now][i].first;
LL way = ko[now][i].second;
if(cost[next] > c + way){
cost[next] = c + way;
que.push(MP(-cost[next],next));
}
}
}
int use = -1;
int now = T[q];
while(now != S[q]){
for(int i=0; i<oya[now].size(); i++){
if(cost[now] == cost[oya[now][i].first]+oya[now][i].second){
for(int j=0; j<K; j++){
if(u[j].first == oya[now][i].first && u[j].second == now) use = j;
}
now = oya[now][i].first;
break;
}
}
}
if(use == 1){
Tap(0);
Tap(0);
}
if(use == 0){
Tap(0);
Tap(1);
}
if(use == -1){
Tap(1);
Tap(0);
Tap(0);
}
if(use == 2){
Tap(1);
Tap(0);
Tap(1);
}
if(use == 3){
Tap(1);
Tap(1);
Tap(0);
}
if(use == 4){
Tap(1);
Tap(1);
Tap(1);
}
}
}
void Bruno(int N, int M, int A[], int B[], long long C[], int Q, int S[], int T[], int K, int U[], int L, int X[]){
vector<pair<int,pair<LL,int> > > ko[300],oya[300];
for(int i=0; i<M; i++){
ko[A[i]].push_back(MP(B[i],MP(C[i],i)));
oya[B[i]].push_back(MP(A[i],MP(C[i],i)));
}
vector<pair<int,int> > u;
for(int i=0; i<K; i++){
u.push_back(MP(A[U[i]],B[U[i]]));
}
int x = 0;
for(int q=0; q<Q; q++){
int use;
if(X[x] == 0){
x++;
if(X[x] == 0){
use = 1;
}
else{
use = 0;
}
}
else{
x++;
if(X[x] == 0){
x++;
if(X[x] == 0){
use = -1;
}
else{
use = 2;
}
}
else{
x++;
if(X[x] == 0){
use = 3;
}
else{
use = 4;
}
}
}
x++;
LL cost[300];
for(int i=0; i<N; i++) cost[i] = LL_MAX;
cost[S[q]] = 0;
priority_queue<pair<LL,int> > que;
que.push(MP(0,S[q]));
while(!que.empty()){
int now = que.top().second;
LL c = -que.top().first;
que.pop();
for(int i=0; i<ko[now].size(); i++){
int next = ko[now][i].first;
LL way = ko[now][i].second.first;
if(way == -1){
way = (LL)10000000000000000;
if(use >= 0 && B[U[use]] == next) way = 1;
}
if(cost[next] > c + way){
cost[next] = c + way;
que.push(MP(-cost[next],next));
}
}
}
vector<int> ans;
ans.push_back(-1);
int now = T[q];
while(now != S[q]){
for(int i=0; i<oya[now].size(); i++){
LL way = oya[now][i].second.first;
if(way == -1){
way = (LL)10000000000000000;
if(use >= 0 && B[U[use]] == now) way = 1;
}
if(cost[now] == cost[oya[now][i].first]+way){
ans.push_back(oya[now][i].second.second);
now = oya[now][i].first;
break;
}
}
}
reverse(ans.begin(), ans.end());
for(int i=0; i<ans.size(); i++) Answer(ans[i]);
}
}