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;
}