5855: 数据结构实验：最短路

#include<bits/stdc++.h>
using namespace std;
int n,m;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,cost;
}a;
vector<edge>G[1005];
double f[1005];
struct p
{
    double first;
    int second;
    bool operator <(const p &w)const
    {
        return first>w.first;
    }
}e,d;
int bfs()
{
    for(int i=1;i<1005;i++)
        f[i]=1000000;
    priority_queue< p > q;
    e.first=0;
    e.second=1;
    q.push(e);
    f[1]=0;
    while(!q.empty())
    {
        e=q.top();
        q.pop();
        int v=e.second;
        if(f[v]<e.first)
         continue;
        for(int i=0;i<G[v].size();i++)
        {
                a=G[v][i];
            if(f[a.to]>f[v]+log10(a.cost))
            {
                f[a.to]=f[v]+log10(a.cost);
                d.first=f[a.to];
                d.second=a.to;
                q.push(d);
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,c;
        scanf("%d%d%d",&x,&y,&c);
        a.to=y;a.cost=c;
        G[x].push_back(a);
    }
    bfs();
    if(f[n]==1000000)
    printf("Sorry\n");
    else
    printf("%d\n",(int)floor(f[n])+1);
}