最短路

【题目描述】

现给定一张N(N <= 1000)个节点的带权有向图，求从1到N的路径中边权之积最小的简单路径。

【输入描述】

第一行输入两个整数N、M(M <= 1000000)，表示节点数目及边数目；

接下来M行，每行输入三个正整数X、Y、Z，表示节点X到节点Y存在一条边权为Z(Z <= 10000)的边。

【输出描述】

输出一个数，表示答案 mod 9987的值。

【输入样例】

3 3

1 2 3

2 3 3

1 3 10

【输出样例】

9

Dijkstra：

源代码：

#include<cstdio>
#include<cmath>
#include<queue>
#include<vector>
#define INF 9987
using namespace std;
struct Node
{
    int To;
    double W;
    bool operator < (const Node &t) const
    {
        if (W==t.W)
          return To<t.To;
        else
          return W>t.W;
    }
};
priority_queue <Node> Q;
vector <Node> List[1001];
int n,m,Ans=1,f[1001],Map[1001][1001];
double i[1001];
void Dijkstra() //Dijkstra+优先队列。
{
    i[1]=0;
    Node t;
    t.To=1;
    t.W=0;
    Q.push(t);
    while (!Q.empty())
    {
        t=Q.top();
        Q.pop();
        for (int a=0;a<List[t.To].size();a++)
        {
            Node T=List[t.To][a];
            if (i[T.To]>t.W+T.W)
            {
                i[T.To]=t.W+T.W;
                T.W=i[T.To];
                Q.push(T);
                f[T.To]=t.To;
            }
        }
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int a=1;a<=n;a++) //double总是不能memset()赋值。
      i[a]=1000000000;
    for (int a=0;a<m;a++)
    {
        Node t;
        int T,S;
        scanf("%d%d%d",&T,&t.To,&S);
        t.W=log(S);
        List[T].push_back(t);
        Map[T][t.To]=S;
    }
    Dijkstra();
    for (int a=n;f[a];a=f[a])
      Ans=Ans*(Map[f[a]][a]%INF)%INF;
    printf("%d",Ans);
    return 0;
}

SPFA：

源代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<queue>
#include<vector>
#define INF 9987
using namespace std;
struct Node
{
    int S,To;
    double W;
};
deque <int> Q;
vector <Node> List[1001];
int n,m,Ans=1,f[1001];
bool In[1001];
double i[1001];
void SPFA() //SPFA+SLF。
{
    i[1]=0;
    In[1]=true;
    Q.push_back(1);
    while (!Q.empty())
    {
        int t=Q.front();
        Q.pop_front();
        In[t]=false;
        for (int a=0;a<List[t].size();a++)
        {
            Node T=List[t][a];
            if (i[T.To]>i[t]+T.W)
            {
                i[T.To]=i[t]+T.W;
                f[T.To]=t;
                if (!In[T.To])
                {
                    In[T.To]=true;
                    if (!Q.empty()&&i[T.To]<i[Q.front()])
                      Q.push_front(T.To);
                    else
                      Q.push_back(T.To);
                }
            }
        }
    }
}
int Find(int t1,int t2)
{
    for (int a=0;a<List[t1].size();a++)
      if (List[t1][a].To==t2)
        return List[t1][a].S;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int a=1;a<=n;a++)
      i[a]=1000000000;
    for (int a=0;a<m;a++)
    {
        int T;
        Node t;
        scanf("%d%d%d",&T,&t.To,&t.S);
        t.W=log(t.S); //数论的结合体，好题。
        List[T].push_back(t);
    }
    SPFA();
    for (int a=n;f[a];a=f[a]) //DFS查找，注意结束条件。
      Ans=Ans*(Find(f[a],a)%INF)%INF;
    printf("%d",Ans);
    return 0;
}

/*
    利用log(N)+log(M)=log(N*M)，即可转化为最短路问题。
*/