spfa（最短路求解）

模板：

#include
    
       #include
     
        #include
      
         #include
       
          using namespace std;  const int maxn = 105;  const int maxm = 100005;  struct Edge{      int to,w,next;  }edge[maxm<<1];  int tot = 0,dis[maxn],cnt[maxn],head[maxn];    void addedge(int u,int v,int w)  {      edge[tot].to = v;edge[tot].w = w;edge[tot].next = head[u];      head[u] = tot++;  }    void spfa(int st,int ed)  {      int i;      queue
        
         que;      while (!que.empty())    que.pop();      memset(dis,0x3f3f3f3f,sizeof(dis));      memset(cnt,0,sizeof(cnt));      que.push(st);      dis[st] = 0;      cnt[st] = 1;      while (!que.empty())      {          int u = que.front();          que.pop();          if (u == ed)    continue;          for (i = head[u];i != -1;i = edge[i].next)          {              int v = edge[i].to;              if (dis[u] + edge[i].w < dis[v])              {                  dis[v] = dis[u] + edge[i].w;                  if (!cnt[v])    que.push(v);                  cnt[v] = cnt[u];              }              else if (dis[u] + edge[i].w == dis[v])              {                  if (!cnt[v])    que.push(v);                  cnt[v] += cnt[u];              }          }      }  }    int main()  {      int N,M,S,E,u,v,w,i;      memset(head,-1,sizeof(head));      scanf("%d%d%d%d",&N,&M,&S,&E);      while (M--)      {          scanf("%d%d%d",&u,&v,&w);          addedge(u,v,w);          addedge(v,u,w);      }      spfa(S,E);      printf("%d %d\n",dis[E],cnt[E]);      return 0;  }