I haven't traveled for a long time! Sensen decided to travel to Z province.
There are n cities in Z province (numbered from 1 to n) and m directional travel routes connecting the two cities (such as self driving, long-distance bus, train, plane, ship, etc.). Each time you pass a travel route, you need to pay the cost of the route (but there may be more than one charging standard. For example, the ticket and air ticket are generally not the same price).
In order to encourage people to visit more in the province, Z province has launched a tourism fund plan: 1 yuan in cash can be exchanged for a in city i i _{i} i ￥ tourist Fund (unlimited exchange as long as there is enough cash). Transportation between cities can be paid in cash or in travel money. Specifically, when passing through the j travel route, c can be used j _{j} j yuan in cash or d j _{j} j ￥ Travel Fund to pay the travel fee. Note: only one payment method can be selected at a time. Cash and travel money cannot be used at the same time. However, for different routes, passengers are free to choose different payment methods.
Sen Sen decided to start from city 1 and go to city n. He plans to prepare some cash before departure, and continue to travel after changing all the remaining cash into tourism gold in a city on the way until he reaches City n. Of course, he can also choose to exchange travel money in City 1, or use all cash to complete the journey.
Z provincial government will adjust the exchange rate according to the participation of each city (i.e. adjust how much tourism money can be exchanged for 1 yuan in cash in a city). Now you need to help Sensen calculate how much cash he needs to carry to complete his journey after each adjustment.
Input format:
Input give three integers n, m and q on the first line (1 ≤ n ≤ 105, 1 ≤ m ≤ 2 × 105, 1 ≤ q ≤ 105), indicating the number of cities, the number of travel routes and the number of exchange rate adjustments in turn.
Next m lines, each line gives four integers u,v, c and d (1 ≤ u,v ≤ n, 1 ≤ c,d ≤ 109), representing a directed travel route from city u to city v. You need to pay c yuan in cash or d yuan in travel money every time you pass the line. Numbers are separated by spaces. The input ensures that starting from city 1, you can reach city n through several routes, but there may be more than one travel route between the two cities, corresponding to different charging standards; It is also allowed to play inside the city (i.e. u and V are the same).
Enter n integers a in the next line 1 _{1} 1,a 2 _{2} 2,⋯,a n _{n} n(1≤a i _{i} i ≤ 109), where a i _{i} i ， means that you can exchange 1 yuan in cash for a in city i at the beginning i _{i} i) a tourist fund. Numbers are separated by spaces.
The next q line describes the exchange rate adjustment. On line i, enter two integers x i _{i} i) and a i _{i} i′(1≤x i _{i} i≤n，1≤a i _{i} I ′≤ 109), indicating x after the i-th exchange rate adjustment i _{i} City i ， can exchange 1 yuan in cash for a i _{i} i ′ tourism gold, while the exchange rate of tourism gold in other cities remains unchanged. Please note: each exchange rate adjustment is based on the previous exchange rate adjustment.
Output format:
For each exchange rate adjustment, output at least how much cash Sen needs to prepare in the corresponding line before he can travel from city 1 to city n according to his plan.
Remind again: if Sensen decides to exchange the travel money in a city on the way, he must exchange all the remaining cash at one time, and the rest of the journey will be paid entirely with the travel money.
Input example:
6 11 3 1 2 3 5 1 3 8 4 2 4 4 6 3 1 8 6 1 3 10 8 2 3 2 8 3 4 5 3 3 5 10 7 3 3 2 3 4 6 10 12 5 6 10 6 3 4 5 2 5 100 1 2 2 1 1 17
Output example:
8 8 1
Example explanation:
For the first exchange rate adjustment, Sensen can travel along the route 1 → 2 → 4 → 6 and exchange tourism money in city 2;
For the second exchange rate adjustment, Sensen can travel along the route of 1 → 2 → 3 → 4 → 6 and exchange tourism gold in city 3;
For the third exchange rate adjustment, Sensen can travel along the route of 1 → 3 → 5 → 6 and exchange tourism money in City 1.
thinking
1. Build the edge forward and run from 1 to the shortest circuit d1[i]
2. Reverse side building and run from n to the shortest circuit d2[i]
3. By enumerating the transfer points, we can get the total amount of cash required in the case of exchanging cash for tourism gold in the ith city = 1 to i shortest path + n to i shortest path
trans[i]=trans[i]=d1[i]+(d2[i]+a[i]-1)/a[i];
Then the answer can be maintained with multiset
Heap optimization dijkstra algorithm priority queue
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,ll> PII;
const int N=1e5+5;
ll INF=1e18+1;//Travel cash first, then travel gold
vector<PII> cash[N],travel[N];
bool st1[N],st2[N];
ll d1[N],d2[N],c,d,ai,a[N],trans[N];
int n,m,q,u,v,xi;
multiset<long long> minCost;
struct node{
int id;
ll dis;
friend int operator < (const node &a, const node &b) {
return a.dis > b.dis;
}
};
priority_queue<node> Q;
void DIJ(int start,vector<PII> cash[],ll d[],bool st[]){
fill(d,d+n+1,INF);
d[start]=0;
Q.push(node{start,0});
while(Q.size()){
int x=Q.top().id;
Q.pop();
if(st[x]) continue;
st[x]=1;
for(int i=0;i<cash[x].size();i++){
if(d[cash[x][i].x]>d[x]+cash[x][i].y){
d[cash[x][i].x]=d[x]+cash[x][i].y;
Q.push(node{cash[x][i].x,d[cash[x][i].x]});
}
}
}
}
int main()
{
cin>>n>>m>>q;
for(int i=0;i<m;i++){
cin>>u>>v>>c>>d;
cash[u].push_back({v,c});
travel[v].push_back({u,d});
}
for(int i=1;i<=n;i++) cin>>a[i];
DIJ(1,cash,d1,st1);
DIJ(n,travel,d2,st2);
for(int i=1;i<=n;i++){//Enumerate transit points
if(d1[i]==INF||d2[i]==INF) continue;
trans[i]=d1[i]+(d2[i]+a[i]-1)/a[i];//More than the whole number, you have to change one more yuan
minCost.insert(trans[i]);
}
for(int i=0;i<q;i++){
cin>>xi>>ai;
if(a[xi]==ai||!trans[xi]) cout<<*minCost.begin()<<endl;
else{
minCost.erase(minCost.find(trans[xi]));
a[xi]=ai;
trans[xi]=d1[xi]+(d2[xi]+a[xi]-1)/a[xi];//More than the whole number, you have to change one more yuan
minCost.insert(trans[xi]);
cout<<*minCost.begin()<<endl;
}
}
return 0;
}
Ordinary dijkstra 19 minutes 3 points running timeout + one wrong answer
#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
typedef pair<int,ll> PII;
const int N=1e5+5;
ll INF=1e18+1;//Travel cash first, then travel gold
vector<PII> cash[N],travel[N];
bool st1[N],st2[N];
ll d1[N],d2[N],c,d,ai,a[N],trans[N];;
int n,m,q,u,v,xi;
multiset<long long> minCost;
void DIJ(int start,vector<PII> cash[],ll d[],bool st[]){
fill(d,d+n+1,INF);
for(int i=0;i<cash[start].size();i++){
d[cash[start][i].x]=cash[start][i].y;
}
st[start]=true;
d[start]=0;
for(int i=1;i<n;i++){
int minpos=0;
for(int j=1;j<=n;j++){
if(!st[j]&&d[minpos]>d[j]) minpos=j;
}
st[minpos]=true;
if(minpos==0) break;
for(int j=0;j<cash[minpos].size();j++){
if(!st[cash[minpos][j].x]&&d[cash[minpos][j].x]>d[minpos]+cash[minpos][j].y)
d[cash[minpos][j].x]=d[minpos]+cash[minpos][j].y;
}
}
}
int main()
{
cin>>n>>m>>q;
for(int i=0;i<m;i++){
cin>>u>>v>>c>>d;
cash[u].push_back({v,c});
travel[v].push_back({u,d});
}
DIJ(1,cash,d1,st1);
DIJ(n,travel,d2,st2);
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=n;i++){//Enumerate transit points
if(d1[i]==INF||d2[i]==INF) continue;
trans[i]=d1[i]+(d2[i]+a[i]-1)/a[i];//More than the whole number, you have to change one more yuan
minCost.insert(trans[i]);
}
for(int i=0;i<q;i++){
cin>>xi>>ai;
if(a[xi]==ai||!trans[xi]) cout<<*minCost.begin()<<endl;
else{
minCost.erase(minCost.find(trans[xi]));
a[xi]=ai;
trans[xi]=d1[xi]+(d2[xi]+a[xi]-1)/a[xi];//More than the whole number, you have to change one more yuan
minCost.insert(trans[xi]);
cout<<*minCost.begin()<<endl;
}
}
return 0;
}