Question
Brief question meaning:
Give you one
n
n
n points
m
m
A graph with m edges. side
i
i
i has color
c
i
c_i
ci?. You can select some edges and change their color to become intervals
[
1
,
m
]
[1,m]
Any color in [1,m], change an edge
i
i
The cost of i once is
w
i
w_i
wi?. Ask if you can make some changes from
1
1
Point 1 can only be reached via the special edge of the current point each time.
n
n
n. The definition of a special edge is: For the current point, the color of the special edge appears in only one of all the outgoing edges of the point. If possible, output the minimum cost. Otherwise output
?
1
-1
?1.
Analysis:
It’s a question with the shortest path based on my feeling.
First of all, there is a property: because the range of colors is the same as the number of edges, so if you want to change an edge, you can change it to a color that no other edge will change again. In other words, If it costs money to change the color of a certain edge, then you can make it colorless, and this is optimal.
Next we consider if an edge
(
u
,
v
)
(u,v)
The color of (u,v) is
c
c
c, the cost is
w
w
w. we start from
u
u
u arrive
v
v
v There are several ways to spend money through it:
1.
u
u
Among the exit edges of u is
c
c
There is only one color of c, then the cost is
0
0
0.
2.
u
u
in the exit edge of u
c
c
There are multiple edges of color c. To change the color of this edge to colorless, the cost is
w
w
w.
3.
u
u
in the exit edge of u
c
c
c There are multiple sides of color. Changing it does not change its color, but changes the color of other sides to colorless.
The cost is
v
a
l
u
,
c
?
w
val_{u, c}-w
valu,cw.
v
a
l
u
,
c
val_{u, c}
valu,c? represents all
u
u
The color of the outgoing edge of u is
c
c
The sum of the costs of the edges of c.
It is not difficult to find that the situation
1
1
1 can be attributed to the situation
3
3
3 in.
Let us consider the problems of treating these two costs as two edge rights running the shortest path:
If according to the situation
3
3
3 from
u
u
u arrive
v
v
v, we consider whether there is a problem: according to the situation
3
3
3 We need to add other colors as well
c
c
The sides of c are all changed to colorless, so will changing it to colorless but not recording it will affect the calculation of the subsequent answer?
The blue points represent the points of the optimal path, and the red edges represent situations.
3
3
The edges dyed colorless in 3 are
c
c
c. The black edges represent the edges of the optimal path. So if the situation shown above occurs (from
5
5
Walk to point 5
1
1
point 1), then
2
2
Arrive on the 2nd
1
1
Point 1 seems to be free of charge because after
4
4
Arrive on the 4th
3
3
At point 3, change the color of that strip to
c
c
The edge of c is dyed colorless. But if we follow the above rules, if we start from
2
2
2 to
3
3
3 Still using the situation
3
3
3. Obviously there will be an extra cost.
But if you think about it a little deeper, that’s not going to happen. Because such a path must not be the optimal path. If you follow the above diagram, then
(
2
,
4
)
(2,4)
(2,4) ,
(
6
,
4
)
(6, 4)
(6,4),
(
4
,
7
)
(4, 7)
(4,7) will be calculated. In fact, if we directly select the path
5
→
4
→
2
→
1
5 \to 4 \to 2 \to 1
5→4→2→1, and
(
4
,
2
)
(4, 2)
(4,2) Usage
2
2
2,
(
2
,
1
)
(twenty one)
(2,1) Usage
3
3
3 is definitely better.
This also means: If we can somehow handle the situation
2
2
2 (that is, the effect of dyeing the edge colorless), then it is correct to run the shortest path according to the above rules.
If according to the situation
2
2
2 After passing a line with color
c
c
The side of c is from
u
u
u arrive
v
v
v, then
(
u
,
v
)
(u,v)
(u,v) The change in color of this edge may affect the
v
v
v to
k
k
k passes through a color of
c
c
c According to the situation
3
3
3 cost. Based on this problem, we consider split points.
A very violent idea is to break down each point into
m
+
1
m+1
m + 1 points: if there are three points
a
a
a,
b
b
b,
c
c
c.
a
a
a to
b
b
b passes through a line with color
x
x
side of x when using the case
2
2
2, it can be obtained from
a
a
a direction
b
x
b_x
bx?, the cost is
0
0
0,
b
x
b_x
bx? must continue along the color x usage
3
3
3 Go to other points. every point
0
0
A status of 0 means No limit. In this way we solve the problem of maintaining information. But the complexity seems to be a problem.
We consider that there is actually no need to open a point
m
m
m points, you only need to open a few points of the existing color for each point. An edge can be provided to two points respectively.
1
1
1 point, so the total number of points is
2
m
+
n
2m+n
2m+n. Then just build the map and run the shortest path. time complexity
O
(
(
n
+
m
)
l
o
g
2
(
n
+
m
)
)
O((n + m)log_2(n + m))
O((n + m)log2?(n + m)). The constant is hundreds of millions of points large.
CODE:
#include<bits/stdc + + .h>//Split the points and split the status of the points
using namespace std;
const int N = 1e5 + 10;
const int M = 2e5 + 10;
const int T = 2 * N + M * 2;
typedef pair< int, int > PII;
typedef long long LL;
inline int read(){<!-- -->
int x = 0, f = 1; char c = getchar();
while(!isdigit(c)){<!-- -->if(c == '-') f = -1; c = getchar();}
while(isdigit(c)){<!-- -->x = (x << 1) + (x << 3) + (c ^ 48); c = getchar();}
return x * f;
}
int u, v, c;
int n, m, head[T], ut[M], vt[M], ct[M], tot, len;//up to T points
bool vis[T];
LL wt[M], dis[T], res, w;
map<PII, int>rk;
map< PII, LL > val;
struct edge{<!-- -->
int v, last;
L w;
}E[M * 8 + 10000];
void add(int u, int v, LL w){<!-- -->
E[ + + len].v = v;
E[len].last = head[u];
E[len].w = w;
head[u] = len;
}
struct state{<!-- -->
int x; LL w;
friend bool operator < (state a, state b){<!-- -->
return a.w > b.w;
}
};
void dijkstra(int s){<!-- -->
priority_queue<state>q;
q.push((state){<!-- -->s, 0});
while(!q.empty()){<!-- -->
state u = q.top(); q.pop();
int x = u.x;
if(vis[x]) continue;
vis[x] = 1;
for(int i = head[x]; i; i = E[i].last){<!-- -->
int v = E[i].v; LL w = E[i].w;
if(dis[v] > dis[x] + w){<!-- -->
dis[v] = dis[x] + w;
q.push((state){<!-- -->v, dis[v]});
}
}
}
}
int main(){<!-- -->
n = read(), m = read();
for(int i = 1; i <= n; i + + ){<!-- -->
rk[make_pair(i, 0)] = + + tot;
}
for(int i = 1; i <= m; i + + ){<!-- -->
u = read(), v = read(); c = read(), w = 1LL * read();
if(!rk[make_pair(u, c)]) rk[make_pair(u, c)] = + + tot;
if(!rk[make_pair(v, c)]) rk[make_pair(v, c)] = + + tot;
val[make_pair(u, c)] + = w;
val[make_pair(v, c)] + = w;
ut[i] = u, vt[i] = v, wt[i] = w, ct[i] = c;
}
for(int i = 1; i <= m; i + + ){<!-- -->
int u = ut[i], v = vt[i], c = ct[i], w = wt[i];
add(rk[make_pair(u, 0)], rk[make_pair(v, 0)], w);//Change color, no restrictions
add(rk[make_pair(u, 0)], rk[make_pair(v, c)], 0);//Change color must be limited
add(rk[make_pair(u, c)], rk[make_pair(v, 0)], val[make_pair(u, c)] - w);
add(rk[make_pair(u, 0)], rk[make_pair(v, 0)], val[make_pair(u, c)] - w);
add(rk[make_pair(v, 0)], rk[make_pair(u, 0)], w);//Change color, no restrictions
add(rk[make_pair(v, 0)], rk[make_pair(u, c)], 0);//Change color must be limited
add(rk[make_pair(v, c)], rk[make_pair(u, 0)], val[make_pair(v, c)] - w);
add(rk[make_pair(v, 0)], rk[make_pair(u, 0)], val[make_pair(v, c)] - w);
}
memset(dis, 0x3f, sizeof dis);
dis[rk[make_pair(1, 0)]] = 0;
dijkstra(rk[make_pair(1, 0)]);
res = dis[rk[make_pair(n, 0)]];
if(res == 0x3f3f3f3f3f3f3f3f) res = -1;
printf("%lld\
", res);
return 0;
}