讨论/题目交流/第64题 求最小路径和 我是用迪杰斯特拉算法做的,单超限,请大佬帮忙看看,感谢/
第64题 求最小路径和 我是用迪杰斯特拉算法做的,单超限,请大佬帮忙看看,感谢

第64题 求最小路径和
我是用迪杰斯特拉算法做的,在提交的时候60/61时,时间超限,想请大佬帮忙看看。
然后想再拓展问个问题:一般时间超限是真的时间超出题目要求的时间限制了?还是说程序的问题
class Solution {
public:
auto fan(map<pair<int,int>,int>& mymap)
{
map<pair<int,int>,int>::iterator it=mymap.begin();
int m=it->second;
auto a=it->first;
for(;it!=mymap.end();it++)
{
if(it->second<m) {m=it->second; a=it->first;}
}
return a;
}
int minPathSum(vector<vector<int>>& grid) {
int r=grid.size();
int c=grid[0].size();
if(r==1&&c==1) return grid[0][0];
map<pair<int,int>,int> mymap;
mymap[{0,0}]=grid[0][0];
int i=0,j=0,m=grid[0][0];
while(1)
{
if(i+1<r)
{
if(!mymap.count({i+1,j})) mymap[{i+1,j}]=mymap[{i,j}]+grid[i+1][j];
else mymap[{i+1,j}]=min( mymap[{i+1,j}],mymap[{i,j}]+grid[i+1][j]);
if((i+2==r)&&(j==c-1)) {m=mymap[{i+1,j}]; break;}
}
if(j+1<c)
{
if(!mymap.count({i,j+1})) mymap[{i,j+1}]=mymap[{i,j}]+grid[i][j+1];
else mymap[{i,j+1}]=min(mymap[{i,j+1}],mymap[{i,j}]+grid[i][j+1]);
if((i+1==r)&&(j+2==c)) {m=mymap[{i,j+1}]; break;}
}
mymap.erase({i,j});
auto a=fan(mymap);
i=a.first;
j=a.second;
}
return m;
}
};

展开讨论

路过,看不懂代码。 这题我看了下是dp啊, 怎么会用dijkstra算法?

展开全部 2 讨论