https://www.acwing.com/problem/content/851/
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=502;
vector<pair<int,int>> son[N];
bool st[N];
int n,m,dist[N];
int dijkstra()
{
dist[1]=0;
st[1]=true;
for(auto k:son[1])
dist[k.first]=k.second;
for(int i=1;i<=n;i++)
{
int t=-1;
for(int j=1;j<=n;j++)
{
if(!st[j]) continue;
for(auto k:son[j])
{
if(!st[k.first]&&(t==-1||dist[t]>dist[k.second]))
t=k.first;
}
}
st[t]=true;
if(t>0)
for(auto k:son[t])
{
if(st[k.first]) continue;
dist[k.first]=min(dist[k.first],dist[t]+k.second);
}
}
if(dist[n]==0x3f3f3f3f) return -1;
else return dist[n];
}
int main()
{
cin>>n>>m;
memset(dist,0x3f,sizeof dist);
while(m--)
{
int a,b,c;
cin>>a>>b>>c;
son[a].push_back({b,c});
}
cout<<dijkstra()<<endl;
return 0;
}
作者:大卵蛋
链接:https://www.acwing.com/problem/content/discussion/content/902/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
后自己cout t值看看吧不要偷懒
(修改代码如下)
dalao,
这个代码感觉也差不多,为啥ac不了
起点都是1吗
是的,我忘记把题目贴出来了
可能会有重边和自环
,会不会你初始化边的权重时,没有取最小值?不会的,最短路过程中 自动取最小值