题目描述
blablabla
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
typedef pair<int,int> PII;
typedef pair<int,PII> PIII;
using node=tuple<int,int,int>;
class Solution {
public:
int get(int x1,int y1,int x2,int y2){
return abs(x1-x2)+abs(y1-y2);
}
int minimumCost(vector<int>& start, vector<int>& target, vector<vector<int>>& specialRoads) {
priority_queue<PIII,vector<PIII>,greater<PIII>> q;
map<PII,int> st;
q.push({0,{start[0],start[1]}});
while(q.size()){
auto t=q.top();
int c=t.first,x=t.second.first,y=t.second.second;
q.pop();
// cout<<x<<" "<<y<<endl;
if(x==target[0]&&y==target[1])
{
return c;
}
if(st.count({x,y})) continue;
st[{x,y}]=c;
q.push({c+get(x,y,target[0],target[1]),{target[0],target[1]}});
for(int i=0;i<specialRoads.size();i++)
{
int a=specialRoads[i][0],b=specialRoads[i][1],cc=specialRoads[i][2],d=specialRoads[i][3];
int e=specialRoads[i][4];
if(!st.count({a,b}))
q.push({c+get(x,y,a,b),{a,b}});
if(x==a&&y==b&&!st.count({cc,d})) q.push({c+e,{cc,d}});
}
}
return 0;
}
};
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla