FAFU - 1283 最短路 - c++编程基础

1.题目：

给你两个数 n，m 表示 n 个点， m 条边

1 <= n <= 1000, 点的范围在 1 - 10w 里。接下来 m 行， 0 <= m <= 10w

每行三个整数 a, b, d

表示从a到b存在着一条距离为d的路径，边为单向边

1 <= a, b <= 10w, 1 <= d <= 1000w，

接下来给你起点和终点，求最短路，如果不联通，

则输出-1

2.代码

#include "stdio.h"  
#include "string"  
#include "queue"  
using namespace std;  
const int M = 100001;  
struct Edge  
{  
    int ed,dis;  
    int next;  
}link[M];  
  
int top, node[M] ;  
__int64 dis[M];  
bool mark[M];  
  
void add(int a, int b,int d)  
{  
    link[top].ed=b;  
    link[top].dis=d;  
    link[top].next = node[a];  //  为a建立连接表  
  
    node[a] = top++;  
}  
  
void spfa(int st, int ed)  
{  
    memset(dis,-1,sizeof(dis));  
    memset(mark,0,sizeof(mark));  
    queue que;  
    que.push(st);  
    dis[st]=0;  
    mark[st]=true;  
    while(!que.empty())  
    {  
        int now = que.front();  
        que.pop();  
        for (int i=node[now];i!=-1;i=link[i].next)  
        {  
            if(dis[link[i].ed]==-1 || dis[link[i].ed]>




dis[now]+link[i].dis)  
            {  
                dis[link[i].ed]=dis[now]+link[i].dis;  
                if(mark[link[i].ed]==false)  
                {  
                    que.push(link[i].ed);  
                    mark[link[i].ed]=true;  
                }  
            }  
  
        }  
        mark[now]=false;  
    }  
}  
  
int main()  
{  
    int n,m, i,a,b,d, st,ed;  
    //freopen("1.txt","r",stdin);  
  
    while(~scanf("%d%d",&n,&m))  
    {  
        top=0;  
        memset(node,-1,sizeof(node));  
        for (i=0;i