2699. Modify Graph Edge Weights
題目:給你一個2D vectors edges: edges[i]={a,b,w}代表a b之間的通行費用為w，給你
一組起終點s,t和一個目標花費target，由於edges的花費存在-1，我們可以將所有花費
為-1的邊的費用任意調整至一正整數，回傳一組修改方案使的這樣的圖從s到t的最短費用
為target，如果不存在此方案則回傳{}
思路:
可以按照提示的思路去想，不存在此方案的原因有
1.原本所有非負邊的邊就足以使s到t最小花費<target
2.將所有負數花費邊的花費調整成1使s到t的最小花費>target
(注意第一種情形是=target時是有可能有解的)
所以我們可以依序執行
1. 先用diijkstra跑非負邊判定有無違反
2. 一次一個將負數邊的費用調整為1，加入adjancy list重跑diijk，如果dist[t]<target
則紀錄當下這個加入邊，否則加入一個set紀錄
3. 如果2.成功了，開始修改edges，遇到負數花費邊則:
-1如果這個邊是2.的紀錄邊則改成1+target-dist[t]
-2如果這個邊存在2.的set則改成花費=1
-3否則，隨便將這個邊花費設成target+1以防干擾結果
注意-1是一定只能改這個邊，不然隨便改存在set中的任一邊成1+target-dist[t]是有可
能錯誤的
vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int
source, int destination, int target) {
set<pair<int,int>> canmod;
vector<vector<pair<int,int>>> testdiij(n,vector<pair<int,int>>());
for(int i=0;i<edges.size();++i){
if(edges[i][2]>0){
testdiij[edges[i][0]].push_back(make_pair(edges[i][2],edges[i][1]));
testdiij[edges[i][1]].push_back(make_pair(edges[i][2],edges[i][0]));
}
else{
canmod.insert(make_pair(edges[i][0],edges[i][1]));
}
}
vector<long long int> dist(n,1000000001);
vector<long long int> testdist(n,1000000001);
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> pq;
testdist[source]=0;
pq.push(make_pair(0,source));
while(!pq.empty()){
int ne_xt=pq.top().second;
pq.pop();
for(auto &neigh:testdiij[ne_xt]){
if(testdist[neigh.second]>testdist[ne_xt]+neigh.first){
testdist[neigh.second]=testdist[ne_xt]+neigh.first;
pq.push(make_pair(testdist[neigh.second],neigh.second));
}
}
}
if(testdist[destination]<target){
return {};
}
set<pair<int,int>> allowchange;
pair<int,int> lgp;
for(auto &jk:canmod){
if(testdist[destination]==1000000001
||testdist[destination]>target){
lgp=jk;
testdiij[jk.first].push_back(make_pair(1,jk.second));
testdiij[jk.second].push_back(make_pair(1,jk.first));
allowchange.insert(jk);
vector<long long int> temp(n,1000000001);
temp[source]=0;
pq.push(make_pair(0,source));
while(!pq.empty()){
int ne_xt=pq.top().second;
pq.pop();
for(auto &neigh:testdiij[ne_xt]){
if(temp[neigh.second]>temp[ne_xt]+neigh.first){
temp[neigh.second]=temp[ne_xt]+neigh.first;
pq.push(make_pair(temp[neigh.second],neigh.second));
}
}
}
testdist=temp;
}
else{
break;
}
}
if(testdist[destination]==1000000001 ||testdist[destination]>target){
return {};
}
else{
if(testdist[destination]==target){
for(auto &g:edges){
if(g[2]<0 && allowchange.count(make_pair(g[0],g[1]))){
g[2]=1;
}
else if(g[2]<0){
g[2]=target+1;
}
}
return edges;
}
else{
for(auto &g:edges){
if(g[2]<0 && allowchange.count(make_pair(g[0],g[1]))
&&make_pair(g[0],g[1])==lgp){
g[2]=1+target-testdist[destination];
notyet=false;
}
else if(g[2]<0 && allowchange.count(make_pair(g[0],g[1]))
&&make_pair(g[0],g[1])!=lgp ){
g[2]=1;
}
else if(g[2]<0 &&
!allowchange.count(make_pair(g[0],g[1]))){
g[2]=target+1;
}
}
}
}
return edges;
}