题意：中文题目
思路：spfa+SLF优化。关于SPFA的详情请戳我
#include <bits/stdc++.h>
using namespace std;
const int N=, INF=0x7f7f7f7f;
int n, m;
bool vis[N]; //标记是否在队列中
int dest[N]; //路径长度
int mapp[N][N]; int spfa(int s, int e) //求最短路径
{
memset(dest,0x7f,sizeof(dest));
dest[s]=;
vis[s]=;
deque<int> que;
que.push_back(s);
while(!que.empty())
{
int tmp=que.front();
que.pop_front();
vis[tmp]=;
for(int i=; i<=n; i++)
{
if(mapp[tmp][i] && dest[tmp]+mapp[tmp][i]<dest[i] )
{
dest[i]=dest[tmp]+mapp[tmp][i];
if(!vis[i]) //一旦被更新，必须进队列
{
vis[i]=;
if(que.empty()) que.push_back(i); //SLF优化，路短的优先放前面
else
{
if(dest[que.front()]>dest[i])
que.push_front(i);
else
que.push_back(i);
}
}
}
}
}
return dest[e];
} int main()
{
//freopen("input.txt", "r", stdin);
int a, b, c;
while(scanf("%d%d", &n, &m), n+m)
{
memset(vis,,sizeof(vis));
memset(mapp,,sizeof(mapp)); for(int i=; i<m; i++)
{
scanf("%d%d%d",&a,&b,&c);
mapp[a][b]=mapp[b][a]=c;
}
printf("%d\n",spfa(,n));
} return ;
}
AC代码
Dijkstra
#include <bits/stdc++.h>
#define LL long long
using namespace std;
const int N=+;
const int INF=0x7f7f7f7f; int g[N][N];
int vis[N];
int dist[N]; int dijkstra(int n)
{
memset(vis,,sizeof(vis));
memset(dist,0x7f,sizeof(dist));
dist[]=;
for(int i=; i<=n; i++) //每次用1个点来更新到其他点的距离
{
int flag, small=INF;
for(int j=; j<=n; j++)//找距离最小的点
{
if(!vis[j]&&dist[j]<=small)
{
small=dist[j];
flag=j;
}
}
vis[flag]=;//标记，不需要再用其更新别人。
for(int j=; j<=n; j++)//有边相连就得更新
{
if(g[j][flag])
dist[j]=min(dist[flag]+g[flag][j], dist[j]);
}
}
return dist[n];
} int main()
{
freopen("input.txt", "r", stdin);
int n, m, a, b, w;
while(scanf("%d%d",&n, &m), n+m)
{
memset(g,,sizeof(g));
for(int i=; i<m; i++)
{
scanf("%d%d%d",&a,&b,&w);
g[a][b]=g[b][a]=w;
}
cout<<dijkstra(n)<<endl;
}
return ;
}
AC代码