Submission #618094
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
struct Initializer {
Initializer() {
cin.tie(0);
ios::sync_with_stdio(0);
cout << fixed << setprecision(15);
}
} initializer;
template <typename T> inline istream& operator>>(istream &s, vector<T> &v) {
for (T &t : v) s >> t;
return s;
}
template <typename T> inline ostream& operator<<(ostream &s, const vector<T> &v) {
for (const T &t : v) s << t << endl;
return s;
}
template<typename T> T min(vector<T>& v) {return *min_element(v.begin(), v.end());}
template<typename T> T max(vector<T>& v) {return *max_element(v.begin(), v.end());}
template<typename T> void sort(vector<T>& v) {sort(v.begin(), v.end());}
template<typename T, typename Function> void sort(vector<T>& v, Function func) {sort(v.begin(), v.end(), func);}
template<typename T> void rsort(vector<T>& v) {sort(v.rbegin(), v.rend());}
template<typename T> void reverse(vector<T>& v) {reverse(v.begin(), v.end());}
template<typename T> void unique(vector<T>& v) {v.erase(unique(v.begin(), v.end()), v.end());}
template<typename T> void nth_element(vector<T>& v, int n) {nth_element(v.begin(), v.begin() + n, v.end());}
template<typename T> bool next_permutation(vector<T>& v) {return next_permutation(v.begin(), v.end());}
template<typename T> int lower_bound(vector<T>& v, T t) {return lower_bound(v.begin(), v.end(), t) - v.begin();}
template<typename T> int upper_bound(vector<T>& v, T t) {return upper_bound(v.begin(), v.end(), t) - v.begin();}
template<typename T> T accumulate(vector<T>& v) {return accumulate(v.begin(), v.end(), T(0));}
template<typename T> void partial_sum(vector<T>& v, vector<T>& u) {partial_sum(v.begin(), v.end(), u.begin());}
template<typename T> T inner_product(vector<T>& v, vector<T>& u) {return inner_product(v.begin(), v.end(), u.begin(), T(0));}
template<typename T, typename Function> void remove_if(vector<T>& v, Function func) {v.erase(remove_if(v.begin(), v.end(), func), v.end());}
template<typename Edge> class Graph {
public:
typedef Edge EdgeType;
virtual int size() const = 0;
template<typename... Args> void addEdge(Args...) {}
template<typename... Args> void addUndirectedEdge(Args...) {}
virtual vector<Edge> getEdges() const = 0;
virtual vector<Edge> getEdges(int from) const = 0;
virtual vector<Edge> getEdges(int from, int to) const = 0;
virtual int getDegree(int v) const = 0;
};
template<typename Edge> class AdjacencyList : public Graph<Edge> {
protected:
vector<vector<Edge>> graph;
public:
AdjacencyList(int n) : graph(n) {}
int size() const {
return graph.size();
}
template<typename... Args> void addEdge(Args... args) {
Edge edge(args...);
graph[edge.from].emplace_back(edge);
}
template<typename... Args> void addUndirectedEdge(Args... args) {
Edge edge(args...);
addEdge(edge);
swap(edge.from, edge.to);
addEdge(edge);
}
vector<Edge> getEdges() const {
vector<Edge> res;
for (const auto& edges : graph) {
res.insert(res.end(), edges.begin(), edges.end());
}
return res;
}
vector<Edge> getEdges(int from) const {
return graph[from];
}
vector<Edge> getEdges(int from, int to) const {
vector<Edge> res;
for (const auto& edge : graph[from]) {
if (edge.to == to) res.emplace_back(edge);
}
return res;
}
int getDegree(int v) const {
return graph[v].size();
}
vector<Edge>& operator[](int v) {
return graph[v];
}
};
struct Edge {
typedef int CostType;
const static int cost = 1;
int from, to;
Edge(int from, int to) : from(from), to(to) {};
};
template<typename Cost> struct WeightedEdge : public Edge {
typedef Cost CostType;
Cost cost;
WeightedEdge(int from, int to, Cost cost = 0) : Edge(from, to), cost(cost) {}
};
template<typename Capacity> struct ResidualEdge : public Edge {
typedef Capacity CapacityType;
Capacity cap;
int rev;
ResidualEdge(int from, int to, Capacity cap) : Edge(from, to), cap(cap) {}
ResidualEdge reverse() const {return ResidualEdge(to, from, 0);}
};
template<typename Capacity, typename Cost> struct WeightedResidualEdge : public ResidualEdge<Capacity> {
Cost cost;
WeightedResidualEdge(int from, int to, Capacity cap, Cost cost) : ResidualEdge<Capacity>(from, to, cap), cost(cost) {}
WeightedResidualEdge reverse() const {return WeightedResidualEdge(this->to, this->from, 0, -cost);}
};
template<typename Graph, typename State> class Search {
protected:
typedef typename Graph::EdgeType Edge;
const Graph graph;
vector<bool> visited;
virtual void push(const State&) = 0;
virtual State next() = 0;
virtual bool isRunning() = 0;
virtual void visit(const State&) {}
virtual bool canPruning(const State&) {return false;}
public:
Search(const Graph& graph) : graph(graph), visited(graph.size(), false) {}
void solve(vector<int> from) {
for (int i : from) push(State(i));
while (isRunning()) {
State now = next();
int pos = now.getPos();
if (visited[pos]) continue;
visited[pos] = true;
visit(now);
for (const Edge& edge : graph.getEdges(pos)) {
State nextState = now.next(edge);
if (visited[nextState.getPos()]) continue;
if (canPruning(nextState)) continue;
push(nextState);
}
}
}
void solve(int from) {solve(vector<int>({from}));}
bool isReachable(int v) {
return visited[v];
}
};
template<typename Edge> class Tree {
public:
vector<Edge> parent;
vector<vector<int>> children;
vector<int> depth;
Tree() {}
Tree(int n) : children(n), depth(n, -1) {
for (int i = 0; i < n; ++i) parent.emplace_back(i, i);
}
int size() const {
return parent.size();
}
template<typename... Args> void addEdge(Args... args) {
Edge edge(args...);
parent[edge.from] = edge;
if (edge.from != edge.to) children[edge.to].emplace_back(edge.from);
}
int getDepth(int v) {
if (depth[v] != -1) return depth[v];
if (parent[v].to == v) return depth[v] = 0;
return depth[v] = getDepth(parent[v].to) + 1;
}
vector<int> getPath(int v) {
vector<int> res{v};
while (v != parent[v].to) {
v = parent[v].to;
res.emplace_back(v);
}
return res;
}
};
template<typename Edge> struct DijkstraState {
typedef typename Edge::CostType Cost;
Edge edge;
Cost cost;
DijkstraState(int pos) : edge(pos, pos), cost(0) {}
DijkstraState(const Edge& edge, Cost cost) : edge(edge), cost(cost) {}
DijkstraState next(const Edge& edge) const {
return DijkstraState(edge, cost + edge.cost);
}
bool operator<(const DijkstraState& state) const {
return cost > state.cost;
}
int getPos() const {
return edge.to;
}
};
template<typename Graph, bool Restoration = false, typename State = DijkstraState<typename Graph::EdgeType>> class Dijkstra : public Search<Graph, State> {
protected:
typedef typename Graph::EdgeType Edge;
typedef typename Edge::CostType Cost;
const Cost INF = numeric_limits<Cost>::max();
priority_queue<State> que;
void push(const State& state) {
que.push(state);
dis[state.getPos()] = state.cost;
}
State next() {
State now = que.top();
que.pop();
return now;
}
bool isRunning() {
return !que.empty();
}
void visit(const State& state) {
if (Restoration) {
auto e = state.edge;
swap(e.from, e.to);
shortestPathTree.addEdge(e);
}
}
bool canPruning(const State& state) {
return dis[state.getPos()] <= state.cost;
}
public:
vector<Cost> dis;
Tree<Edge> shortestPathTree;
Dijkstra(const Graph& graph) : Search<Graph, State>(graph), dis(graph.size(), INF) {
if (Restoration) shortestPathTree = Tree<Edge>(graph.size());
}
};
template<typename Graph> inline Dijkstra<Graph> shortestPath(Graph& graph, int from) {
Dijkstra<Graph> dijkstra(graph);
dijkstra.solve(from);
return dijkstra;
}
template<typename Graph> inline typename Graph::EdgeType::CostType shortestPath(Graph& graph, int from, int to) {
Dijkstra<Graph> dijkstra(graph);
dijkstra.solve(from);
return dijkstra.dis[to];
}
template<typename Graph> inline Dijkstra<Graph, true> shortestPathTree(Graph& graph, int from) {
Dijkstra<Graph, true> dijkstra(graph);
dijkstra.solve(from);
return dijkstra;
}
struct MyEdge : public WeightedEdge<int> {
int end, endcost;
MyEdge(int from, int to, int cost = 0, int end = 0, int endcost = 0) : WeightedEdge<int>(from, to, cost), end(end), endcost(endcost) {}
};
struct MyState : public DijkstraState<MyEdge> {
static vector<int> dis;
MyState(int pos) : DijkstraState<MyEdge>(pos) {}
MyState(const MyEdge& edge, Cost cost) : DijkstraState<MyEdge>(edge, cost) {}
MyState next(const MyEdge& edge) const {
return MyState(edge, max(cost + edge.cost, edge.endcost + dis[edge.end]));
}
};
vector<int> MyState::dis;
int main() {
int n, m, src, dst;
cin >> n >> m >> src >> dst;
vector<int> l(m);
vector<vector<int>> s(m), w(m);
AdjacencyList<MyEdge> graph(n);
for (int i = 0; i < m; ++i) {
cin >> l[i];
s[i].resize(l[i]);
w[i].resize(l[i] - 1);
cin >> s[i] >> w[i];
int sum = accumulate(w[i]);
int s1 = sum, s2 = sum;
for (int j = 0; j < l[i] - 1; ++j) {
graph[s[i][j + 1]].emplace_back(s[i][j + 1], s[i][j], w[i][j], s[i].back(), s1);
s1 -= w[i][j];
}
for (int j = l[i] - 1; j >= 1; --j) {
graph[s[i][j - 1]].emplace_back(s[i][j - 1], s[i][j], w[i][j - 1], s[i][0], s2);
s2 -= w[i][j - 1];
}
}
MyState::dis = shortestPath(graph, dst).dis;
Dijkstra<AdjacencyList<MyEdge>, false, MyState> dijkstra(graph);
dijkstra.solve(dst);
cout << dijkstra.dis[src] << endl;
}
Submission Info
Submission Time |
|
Task |
C - メンテナンス明け |
User |
not |
Language |
C++11 (GCC 4.9.2) |
Score |
100 |
Code Size |
9718 Byte |
Status |
AC |
Exec Time |
101 ms |
Memory |
8096 KB |
Judge Result
Set Name |
Subtask1 |
Subtask2 |
Score / Max Score |
50 / 50 |
50 / 50 |
Status |
|
|
Set Name |
Test Cases |
Subtask1 |
small/00_sample00, small/00_sample01, small/00_sample02, small/10_small-0000, small/10_small-0001, small/10_small-0002, small/10_small-0003, small/10_small-0004, small/10_small-0005, small/10_small-0006, small/10_small-0007, small/10_small-0008, small/10_small-0009, small/10_small-0010, small/10_small-0011, small/10_small-0012, small/10_small-0013, small/10_small-0014, small/10_small-0015, small/10_small-0016, small/10_small-0017, small/10_small-0018, small/10_small-0019, small/30_max_small, small/40_simple_0000, small/40_simple_0001, small/40_simple_0002, small/40_simple_0003, small/40_simple_0004, small/40_simple_0005, small/40_simple_0006, small/40_simple_0007, small/40_simple_0008, small/40_simple_0009, small/40_simple_0010, small/40_simple_0011, small/40_simple_0012, small/40_simple_0013, small/40_simple_0014, small/40_simple_0015, small/40_simple_0016, small/40_simple_0017, small/40_simple_0018, small/40_simple_0019, small/90_dijkstra_killer_00, small/90_dijkstra_killer_01, small/91_tayama_killer_00, small/91_tayama_killer_01, small/91_tayama_killer_02, small/91_tayama_killer_03, small/91_tayama_killer_04, small/91_tayama_killer_05 |
Subtask2 |
large/20_large-00, large/20_large-01, large/20_large-02, large/20_large-03, large/20_large-04, large/31_max_large |
Case Name |
Status |
Exec Time |
Memory |
large/20_large-00 |
AC |
100 ms |
8084 KB |
large/20_large-01 |
AC |
101 ms |
8080 KB |
large/20_large-02 |
AC |
101 ms |
8076 KB |
large/20_large-03 |
AC |
100 ms |
8096 KB |
large/20_large-04 |
AC |
101 ms |
8076 KB |
large/31_max_large |
AC |
57 ms |
4688 KB |
small/00_sample00 |
AC |
25 ms |
920 KB |
small/00_sample01 |
AC |
27 ms |
796 KB |
small/00_sample02 |
AC |
24 ms |
800 KB |
small/10_small-0000 |
AC |
26 ms |
800 KB |
small/10_small-0001 |
AC |
26 ms |
920 KB |
small/10_small-0002 |
AC |
25 ms |
924 KB |
small/10_small-0003 |
AC |
24 ms |
928 KB |
small/10_small-0004 |
AC |
26 ms |
804 KB |
small/10_small-0005 |
AC |
26 ms |
796 KB |
small/10_small-0006 |
AC |
24 ms |
800 KB |
small/10_small-0007 |
AC |
24 ms |
792 KB |
small/10_small-0008 |
AC |
25 ms |
924 KB |
small/10_small-0009 |
AC |
25 ms |
796 KB |
small/10_small-0010 |
AC |
25 ms |
928 KB |
small/10_small-0011 |
AC |
24 ms |
800 KB |
small/10_small-0012 |
AC |
24 ms |
800 KB |
small/10_small-0013 |
AC |
23 ms |
800 KB |
small/10_small-0014 |
AC |
24 ms |
924 KB |
small/10_small-0015 |
AC |
24 ms |
800 KB |
small/10_small-0016 |
AC |
26 ms |
920 KB |
small/10_small-0017 |
AC |
24 ms |
804 KB |
small/10_small-0018 |
AC |
25 ms |
924 KB |
small/10_small-0019 |
AC |
25 ms |
924 KB |
small/30_max_small |
AC |
25 ms |
928 KB |
small/40_simple_0000 |
AC |
23 ms |
928 KB |
small/40_simple_0001 |
AC |
23 ms |
928 KB |
small/40_simple_0002 |
AC |
27 ms |
804 KB |
small/40_simple_0003 |
AC |
28 ms |
800 KB |
small/40_simple_0004 |
AC |
26 ms |
804 KB |
small/40_simple_0005 |
AC |
25 ms |
928 KB |
small/40_simple_0006 |
AC |
26 ms |
804 KB |
small/40_simple_0007 |
AC |
26 ms |
816 KB |
small/40_simple_0008 |
AC |
27 ms |
804 KB |
small/40_simple_0009 |
AC |
26 ms |
800 KB |
small/40_simple_0010 |
AC |
25 ms |
804 KB |
small/40_simple_0011 |
AC |
24 ms |
924 KB |
small/40_simple_0012 |
AC |
26 ms |
804 KB |
small/40_simple_0013 |
AC |
24 ms |
796 KB |
small/40_simple_0014 |
AC |
25 ms |
928 KB |
small/40_simple_0015 |
AC |
25 ms |
804 KB |
small/40_simple_0016 |
AC |
26 ms |
800 KB |
small/40_simple_0017 |
AC |
27 ms |
800 KB |
small/40_simple_0018 |
AC |
30 ms |
772 KB |
small/40_simple_0019 |
AC |
27 ms |
916 KB |
small/90_dijkstra_killer_00 |
AC |
28 ms |
844 KB |
small/90_dijkstra_killer_01 |
AC |
27 ms |
796 KB |
small/91_tayama_killer_00 |
AC |
27 ms |
920 KB |
small/91_tayama_killer_01 |
AC |
25 ms |
796 KB |
small/91_tayama_killer_02 |
AC |
26 ms |
928 KB |
small/91_tayama_killer_03 |
AC |
26 ms |
804 KB |
small/91_tayama_killer_04 |
AC |
26 ms |
808 KB |
small/91_tayama_killer_05 |
AC |
26 ms |
800 KB |