#include <cstdio>
#include <iostream>
#include <cstring>
#define INF 999999999
using namespace std;
int nump,vh,ve;
int pa[1010][1010];
int vis[1010];
void Dijkstra(int v,long long dist[])
{
int i,j,k=0;
dist[v] = 0;
vis[v] = 0;
for (i = 1; i < 1001; i++)
{
long long min = INF;
for (j = 0; j < 1001; j++)
if (vis[j] && dist[j] < min)
{
k = j;
min = dist[j];
}
vis[k]=0;
for (int w = 0; w < 1001; w++)
if (vis[w] && dist[w] > dist[k] + pa[k][w])
dist[w] = dist[k] + pa[k][w];
}
}

int main()
{
memset(vis,0,sizeof(vv1));
for(int i=0;i<1001;i++)
for(int j=0;j<1001;j++)
pa[i][j]=INF;
scanf("%d",&nump);
for(int i=0;i<nump;i++)
{
int vx,vy,v;
scanf("%d%d%d",&vx,&vy,&v);
pa[vx][vy]=pa[vy][vx]=v;
vis[vx]=vis[vy]=1;
}
scanf("%d%d",&vh,&ve);
long long dist[1001];
for(int i=0;i<1001;i++)
dist[i]=INF;
Dijkstra(vh,dist);
if(dist[ve]==INF)
cout<<"Inf"<<endl;
else
cout<<dist[ve]<<endl;
return 0;
}

/*

*/
#define method_1
#ifdef method_1
/*

*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<vector>
#include<cstring>
#include<cstdlib>
using namespace std;
typedef long long ll;
const int maxn=5000+5;
const int INF=0x3f3f3f3f;
struct node {
    int u,v,c;
} edge[maxn*maxn];
int head[maxn];
int cnt=0;
void add(int from,int to,int val) {
    edge[++cnt].v=to;
    edge[cnt].c=val;
    edge[cnt].u=head[from];
    head[from]=cnt;
}
int n,m;
int d[maxn],vis[maxn];
void spfa(int s) {
    queue<int>q;
//  q.clear();
    vis[s]=1;
    d[s]=0;
    q.push(s);
    while(!q.empty()) {
        int from=q.front();
        q.pop();
        vis[from]=0;
        for(int i=head[from]; ~i; i=edge[i].u) {
            int to=edge[i].v;
            int val=edge[i].c;
            if(d[from]+val<d[to]) {
                d[to]=d[from]+val;
                if(!vis[to]) {
                    q.push(to);
                    vis[to]=1;
                }
            }
        }
    }
}
int sv,ev;
int main() {
    ios::sync_with_stdio(false);
//  freopen("最短路径.in","r",stdin);
    memset(head,-1,sizeof(head));
    memset(vis,0,sizeof(vis));
    memset(d,INF,sizeof(d));
    cin>>n;
    int a,b,w;
    for(int i=1; i<=n; i++) {
        cin>>a>>b>>w;
        add(a,b,w);
        add(b,a,w);
    }
    cin>>sv>>ev;
    spfa(sv);
//  cout<<d[600];
    if(d[ev]!=INF) cout<<d[ev];
    else cout<<"Inf";
    return 0;
}
#endif
#ifdef method_2
/*

*/

#endif
#ifdef method_3
/*

*/

#endif

写在开头：非官方题解，加上比较菜，说错的地方还望指正。

1.理思路：这不最典型的最短路径吗？还理个啥。

2.选做法：求单源最短路径，我选dijkstra。不过BF，SPFA应该也可以吧，没试过。顶点数最大1000的话，Floyd的O(n^3)应该不行，也没有必要跑多源。存储方式就邻接矩阵。

3.注意：a.该题的路径均为无向路径。
b.测试点的话，怀疑老师是rand()循环打印的，然后改了几个数据，改出一条路。
c.di数据范围没给，用long long 防溢出。
4.参考源码（写法可能不正统）

#include <cstdio>
#include <iostream>
#include <cstring> 
#define INF 999999999
using namespace std;
int nump,vh,ve;
int pa[1010][1010];
int vis[1010];
void Dijkstra(int v,long long dist[])
{
    int i,j,k=0;
    dist[v] = 0;
    vis[v] = 0;
    for (i = 1; i < 1001; i++)
    {
        long long min = INF;
        for (j = 0; j < 1001; j++)
            if (vis[j] && dist[j] < min)
            {
                k = j;
                min = dist[j];
            }
        vis[k]=0;
        for (int w = 0; w < 1001; w++)
            if (vis[w] && dist[w] > dist[k] + pa[k][w])
                dist[w] = dist[k] + pa[k][w];
    }
}

int main()
{
    memset(vis,0,sizeof(vv1));
    for(int i=0;i<1001;i++)
        for(int j=0;j<1001;j++)
            pa[i][j]=INF;
    scanf("%d",&nump);
    for(int i=0;i<nump;i++)
    {
        int vx,vy,v;
        scanf("%d%d%d",&vx,&vy,&v);
        pa[vx][vy]=pa[vy][vx]=v;
        vis[vx]=vis[vy]=1;
    }
    scanf("%d%d",&vh,&ve);
    long long dist[1001];
    for(int i=0;i<1001;i++)
        dist[i]=INF;
    Dijkstra(vh,dist);
    if(dist[ve]==INF)
        cout<<"Inf"<<endl;
    else 
        cout<<dist[ve]<<endl;
    return 0;
}