F - ヘビの JOI 君に挑戦したのですがTLEになります。
しかし、なぜ自分のコードが非効率なのかがわかりません。コードの問題点などを教えていただけないでしょうか。下が自分のコードです。
int N, M,X,T[10000];
struct edge{
int to,cost;
};
struct situ {
int cost,v,dist,type;
bool operator<(const situ& rhs) const
{
return cost < rhs.cost;
}
};
vector<edge>G[10005];
int d[10005][205][3];
void dijkstra(int s) {
d[0][0][0] = 0;
priority_queue<situ> que;
que.push({ 0, s, 0,0 });
while (!que.empty()) {
situ p = que.top(); que.pop();
int cost = p.cost, v = p.v;
if (d[v][p.dist][p.type] < cost)continue;
for (edge u : G[v]) {
if (abs(p.type - T[u.to]) > 1 && p.dist+u.cost < X) {
continue;
}
int type = p.type,dist = min(p.dist + u.cost,X);
if (T[u.to] != 1) {
type = T[u.to];
dist = 0;
}
if (d[u.to][dist][type] > d[v][p.dist][p.type] + u.cost) {
d[u.to][dist][type] = d[v][p.dist][p.type] + u.cost;
que.push({ d[u.to][dist][type],u.to,dist,type });
}
}
}
}
int main()
{
cin >> N >> M >> X;
rep(i, N) {
cin >> T[i];
}
rep(i, M) {
int a, b,d;
cin >> a >> b >> d;
a--; b--;
G[a].push_back({ b,d });
G[b].push_back({ a,d });
}
rep(i, N) {
rep(j, X + 1) {
fill_n(d[i][j], 3, INF);
}
}
dijkstra(0);
N--;
int ans = INF;
rep(i, X+1) {
rep(j, 3) {
ans = min(ans, d[N][i][j]);
}
}
cout << ans << endl;
}
次にサンプルコード
#include<cstdio>
#include<vector>
#include<utility>
#include<queue>
using namespace std;
const int MAX_N = 10000;
const int MAX_X = 200;
const int inf = 1e9;
struct Edge{
int to, cost;
Edge(){}
Edge(int to, int cost):to(to), cost(cost){}
};
vector<Edge> G[MAX_N];
int color[MAX_N]; //temperature (0/1/2)
int N, X;
int dis[MAX_N][2][MAX_X + 1];
typedef pair<int, int> P; //<temperature of the nearest non-comfortable room (0 or 2), distance from there>
typedef pair<int, P> P2; //<vertex, P>
typedef pair<int, P2> P3; //<distance from s, P2>
P update_state(P p, Edge e){
if(color[e.to] == 0){
if(p.first == 2 && p.second + e.cost < X){
return P(-1, -1);
}else{
return P(0, 0);
}
}else if(color[e.to] == 1){
int d = min(X, p.second + e.cost);
return P(p.first, d);
}else{
if(p.first == 0 && p.second + e.cost < X){
return P(-1, -1);
}else{
return P(2, 0);
}
}
}
void dijkstra(){
priority_queue<P3, vector<P3>, greater<P3> > que;
for(int i = 0; i < N; ++i){
for(int j = 0; j < 3; ++j){
for(int k = 0; k < MAX_X + 1; ++k){
dis[i][j][k] = inf;
}
}
}
dis[0][0][0] = 0;
que.push(P3(0, P2(0, P(0, 0))));
while(!que.empty()){
P3 p3 = que.top();
que.pop();
int d = p3.first;
int v = p3.second.first;
P prv_state = p3.second.second;
if(dis[v][prv_state.first / 2][prv_state.second] < d) continue;
for(int i = 0; i < G[v].size(); ++i){
P np = update_state(prv_state, G[v][i]);
if(np == P(-1, -1)) continue;
int nd = d + G[v][i].cost;
int nv = G[v][i].to;
if(dis[nv][np.first / 2][np.second] <= nd) continue;
dis[nv][np.first / 2][np.second] = nd;
que.push(P3(nd, P2(nv, np)));
}
}
}
int solve(){
dijkstra();
int ans = inf;
for(int c = 0; c < 2; ++c){
for(int d = 0; d <= X; ++d){
ans = min(ans, dis[N - 1][c][d]);
}
}
for(int v = 0; v < N; ++v){
int tmp = inf;
for(int c = 0; c < 2; ++c){
for(int d = 0; d <= X; ++d){
tmp = min(tmp, dis[v][c][d]);
}
}
}
return ans;
}
void input(){
int M;
scanf("%d%d%d", &N, &M, &X);
for(int i = 0; i < N; ++i){
scanf("%d", color + i);
}
for(int i = 0; i < M; ++i){
int u, v, d;
scanf("%d%d%d", &u, &v, &d);
u--;
v--;
G[u].push_back(Edge(v, d));
G[v].push_back(Edge(u, d));
}
}
int main(){
input();
int ans = solve();
printf("%d\n", ans);
return 0;
}
ちなみにサンプルコードは最悪でも実行時間60msです。
制約などは最初のURLに載っています。
追記:
自分のコードの省略した部分です
#define _USE_MATH_DEFINES
#include<math.h>
//#include<cmath>
#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
#include<memory>
//#include "Ants.h"
using namespace std;
typedef long long ll;
#define rad_to_deg(rad) (((rad)/2/M_PI)*360)
#define EPS (1e-7)
#define INF (1e9)
#define PI (acos(-1))
#define rep(i,n) for(int i=0;i<n;i++)
#define show(s) cout<<s<<endl
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define LINF (1000000000000000000ll)
typedef pair<int, int> P;