最短パターン(Floyd+bellman+spfa+Dijkstra)

さいたんらくもんだい
1、単一ソース最短
a、所有権エッジはすべて正数です.
Dijkstraアルゴリズム:素朴アルゴリズム(O(mn))スタック最適化(O(mlogn))
b、負数の変化がある:
Bellmanアルゴリズム:O(mn)
Spfaアルゴリズム:(一般状況O(m),最悪状況O(mn))(慎重)
 
2、マルチソース最短
Floydアルゴリズム:O(n^3)
 
Dijkstra

#include
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int NUM = 1005;
struct edge{
	int from,to,w;
	edge(int a,int b,int c){from=a;to=b;w=c;}
};
vectore[NUM];
struct s_node{
	int id,n_dis;
	s_node(int b,int c){id=b;n_dis=c;}
	bool operator < (const s_node &a) const
	{return n_dis>a.n_dis;}
};
int n,m;
int pre[NUM];
void print_path(int s,int t)
{
	if(s==t)printf("%d",s);
	print_path(s,pre[t]);
	printf("%d",t);
}
void Dijkstra(int s)  //s   
{
    int dis[NUM];
    bool done[NUM];
    for(int i=1;i<=n;i++){dis[i]=INF;done[i]=false;}
    dis[s]=0;
    ;priority_queueQ
    Q.push(s_node(s,dis[s]));
    while(!Q.empty())
    {
    	s_node u=Q.top();
        Q.pop();
        if(done[u.id])continue;
        done[u.id]=true;
        for(int i=0;iy.w+u.n_dis){
        		dis[y.to]=y.w+u.n_dis;
        		Q.push(s_node(y.to,dis[y.to]));
        		pre[y.to]=u.id;
        	}
        }
    }
    printf("%d
",dis[n]);
}
int main()
{
    while(~scanf("%d %d",&n,&m)){
    	if(n==0&&m==0)break;
    	for(int i=1;i<=n;i++){
    		e[i].clear();
    	}
    	for(int i=1;i<=m;i++){
    		int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            e[a].push_back(edge(a,b,c));
            e[b].push_back(edge(b,a,c));
    	}
    	Dijkstra(1);
    }
	return 0;
}

//  
//-----------------------
const int NUM = 1005;
int mp[NUM][NUM];
int dis[NUM];
bool vis[NUM];
int n,m;
void Dijkstra()
{
    int pos=1,minn;
    for(int i=1;i<=n;i++)vis[i]=false;
    dis[1]=0;
    vis[1]=1;
    for(int i=1;i<=n;i++){
        minn=INF;
        for(int j=1;j<=n;j++){
            if(vis[j]==0&&minn>dis[j]){
                minn=dis[j];
                pos=j;
            }
        }
        vis[pos]=1;
        for(int j=1;j<=n;j++){
            if(vis[j]==0&&dis[j]>dis[pos]+mp[pos][j]){
                dis[j]=dis[pos]+mp[pos][j];
            }
        }
    }
    printf("%d
",dis[n]);
}

Bellman

#include 
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int NUM = 105;
struct edge{int u,v,w;}e[10005];
int n,m,cnt;
int pre[NUM];
void print_path(int s,int t)
{
    if(s==t){printf("%d",s); return 0;}
    print_path(s,pre[t]);
    printf("%d",t);
}
void bellman(int s)
{
    int d[NUM];
    for(int i=1;i<=n;i++)d[i]=INF;
    d[s]=0;
    for(int k=1;k<=n;k++){
        for(int i=0;id[y]+e[i].w){
                d[x]=d[y]+e[i].w;
                pre[x]=y;
            }
        }
    }
    printf("%d
",d[n]);
}

//----------------------------
void bellman(int s) //  
{
   int d[NUM];
   for(int i=1;i<=n;i++)d[i]=INF;
   d[s]=0;
   int k=0;
   bool update=true;
   while(update){
     k++;
     if(k>n){printf("   ");}
     for(int i=0;id[y]+e[i].w){
          update=true;
          d[x]=d[y]+e[i].w;
          //pre[x]=y;
       }
     }
   }
   printf("%d
",d[n]);
}


int main()
{
    while(~scanf("%d %d",&n,&m)){
        if(n==0||m==0)break;
        cnt=0;
        for(int i=1;i<=m;i++){
            int a,b,c;
            scanf("%d %d %d",&a,&b,&c);
            e[cnt].u=a; e[cnt].v=b; e[cnt].w=c; cnt++;
            e[cnt].u=b; e[cnt].v=a; e[cnt].w=c; cnt++;
        }
        bellman(1);   // 1 n    
    }
    return 0;
}

spfa

#include
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int NUM=105;
struct edge{
	int to,next,w;
	edge(int a,int b,int c){to=a;next=b;w=c;}
};
vectore[NUM];
int n,m;
int pre[NUM];
void print_path(int s,int t)
{
   if(s==t)printf("%d",s);
   print_path(s,pre[t]);
   printf("%d",t);
}
void spfa(int s)
{
    int dis[NUM];
    bool inq[NUM];
    int neg[NUM];
    for(int i=1;i<=n;i++){dis[i]=INF;inq[i]=false;neg[i]=0;}
    dis[s]=0;
	neg[s]=1;
	queueQ;
	Q.push(s);
	inq[s]=true;
	while(!Q.empty())
	{
		int u=Q.front();
		Q.pop();
		inq[u]=false;
		for(int i=0;idis[u]+w){
				dis[v]=dis[u]+w;
				pre[v]=u;
				if(!inq[v]){
                   Q.push(v);
                   inq[v]=true;
                   neg[v]++;
                   if(neg[v]>n){printf("   
");return;}
				}
			}
		}
	}
	printf("%d
",dis[n]);
	return;
}
int main()
{
	while(~scanf("%d %d",&n,&m)){
		if(n==0&&m==0)break;
		for(int i=1;i<=n;i++){
			e[i].clear();
		}
		for(int i=1;i<=m;i++){
			int a,b,c;
			scanf("%d %d %d",&a,&b,&c);
			e[a].push_back(edge(a,b,c));
			e[b].push_back(edge(b,a,c));
		}
		spfa(1);
	}
	return 0;
}

Floyd

#include
#define ll long long
#define MOD 998244353 
#define INF 0x3f3f3f3f
#define mem(a,x) memset(a,x,sizeof(a))  
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int NUM = 105;
int graph[NUM][NUM];
int n,m;
void Floyd(int s)
{
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			if(graph[i][k]!=INF){
				for(int j=1;j<=n;j++){
					if(graph[i][k]+graph[k][j]