1382：最短路(Spfa)
时间限制: 1000 ms 内存限制: 65536 KB
提交数: 5653 通过数: 1599
【题目描述】
给定 MM 条边， NN 个点的带权无向图。求 11到 NN 的最短路。
【输入】
第一行：N,M(N≤100000，M≤500000)N,M(N≤100000，M≤500000)；
接下来MM行33个正整数：ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000ai,bi,ci表示ai,bi之间有一条长度为ci的路，ci≤1000。
【输出】
一个整数，表示 11 到 NN 的最短距离。
【输入样例】
4 4
1 2 1
2 3 1
3 4 1
2 4 1
【输出样例】
2
【提示】
【样例解释】
注意图中可能有重边和自环,数据保证 11 到 NN 有路径相连。
思路：spfa，我这里犯了个小错误，花了我1h找一找（'__')。
#include <bits/stdc++.h>
using namespace std;
int n,m,x,y,z,dis[100005];
bool vis[100050];
struct wow
{
int num,di;
};
vector <wow> b[100005];
int main()
{
cin>>n>>m;
for(int i=1; i<=m; i++)
{
scanf("%d%d%d",&x,&y,&z);
wow c;
if(x!=y)//排除自环
{
c.num=x;
c.di=z;
b[y].push_back(c);
c.num=y;
b[x].push_back(c);
}
}//输入
queue<int> q;
memset(dis,0x3f,sizeof(dis));
dis[1]=0;//初值
vis[1]=1;//访问过
q.push(1);
while(!q.empty())
{
int c=q.front();
q.pop();
vis[c]=0;
for(int i=0; i<b[c].size(); i++)
{
wow d=b[c][i];
if(dis[d.num]>d.di+dis[c])
{
dis[d.num]=d.di+dis[c];
if(vis[d.num]==0)
{
vis[d.num]=1;
q.push(d.num);
}
}
}
}//spfa
cout<<dis[n]<<endl;//输出
return 0;
}
Simon说：
好久前写的文章，我欠的债……今天才发。
说声对不起哦，好久没写了。
不过，我会补上的……
风萧萧兮易水寒，欠了债兮你要还。
我会还的（'_')。
再见。
