dijkstra板子-白红宇

dijkstra板子

阅读量：3953 次

发布时间：2019-05-24

本文共 2105 字，大约阅读时间需要 7 分钟。

描述

给定带权无向图G(V,E)和源点s/终点t，求一条 s->t 的最短路径。假设读入边的列表是有（字典）序的（既邻接表就是有序的）。

输入

第一行包含4个整数N、M、s、t，表示该图共有N个结点和M条无向边。（N <= 5000，M <= 200000）。起点为s，终点为t

接下来M行，每行包含3个整数{u,v,w}，表示有一条权值为w的无向边连接结点u、v

输出

输出最短路的长度

若无法到达，输出"No path"

样例输入

4 5 1 41 2 21 3 11 4 52 4 33 4 5

样例输出

#include
   
    #include
    
     #include 
     
      using namespace std;typedef long long ll;typedef pair
      
        PII;struct Node{    int var,next,val;} edge[100000005];int head[100005],tot,dis[100005],N,M;bool vis[100005];priority_queue
       
         Q;void add(int a, int b, int c){    edge[++tot].var = b;    edge[tot].val = c;    edge[tot].next = head[a];    head[a] = tot;}void init()//多组输入调用{    tot=0;    memset(head,0,sizeof(head));}void dijkstra(int s){    memset(dis,0x3f,sizeof(dis));    //memset(vis,0,sizeof(vis));    //while(Q.size()) Q.pop();    dis[s] = 0;    Q.push(make_pair(0,s));    while(!Q.empty())    {        int x=Q.top().second;        Q.pop();        if(vis[x])continue;        vis[x]=1;        for(int i=head[x]; i; i=edge[i].next)        {            int y=edge[i].var;            if(dis[x]+edge[i].val

用map容器把字符串改换成对应的int型数字，另外就是要记录下一共出现了多少不同的字符串

#include
   
    #include
    
     #include
     #include
      
       #include
       
        using namespace std;const int INF=0x3f3f3f3f;int n,mm,ans;char s1[105],s2[105];bool vis[2000];int tu[105][105];int num[105];int dijkstra(int a,int b)  //找两点间的最短路{    memset(vis,0,sizeof(vis));    for(int i=a;i<=b;i++)        num[i]=tu[a][i];    num[a]=0;    for(int i=a;i<=b;i++)    {        int min=INF,u=-1;        for(int j=a;j<=b;j++)        {            if(!vis[j]&&num[j]
        
         num[u]+tu[k][u]) num[k]=num[u]+tu[k][u]; } return num[2];}int main(){ map
         
           m; //定义一个map函数 名为mat； ios::sync_with_stdio(false); while(cin>>n&&n>=0) { m.clear(); //清空mat； memset(tu,INF,sizeof(tu)); cin>>s1>>s2; int flag=0; if(!strcmp(s1,s2)) //判断起点和终点是否相等； flag=1; m[s1]=1; //s1用数字1表示； 字符数字化； m[s2]=2; ans=2; //从2开始代替标识； for(int i=0;i
          
           >s1>>s2>>mm; if(!m[s1]) //判断是否与起点相同；不同加以1； 相等时mat[s1]=1；不等=0； m[s1]=++ans; if(!m[s2]) //判断是否与终点相同；不同加以1； m[s2]=++ans; if(mm