<?php
echo "<meta http-equiv='Content-Type' content='text/html;charset=utf-8'>";
error_reporting( E_ALL&~E_NOTICE );
define("Inf",0x7fffffff);
define("MaxV",10000);
define("MaxE",10000);
class Edge
{
var $to,$nex,$w;
function __construct($to,$nex,$w)
{
$this->to=$to;
$this->nex=$nex;
$this->w=$w;
}
}
class A
{
public $N,$M;
public $edge = array();
public $size;
public $head = array();
public $dist = array();
public $cot = array();
public $vst = array();
public $path = array();
function InsertEdge($from,$to,$w)
{
$this->edge[$this->size] = new Edge($to,$this->head[$from],$w);
$this->head[$from] = $this->size++;
}
function spfa($s)
{
$from;
$to;
$que = new queue(30);
for($i=0;$i<=$this->N;$i++){
$this->path[$i]=$i;
$this->dist[$i]=Inf;
}
$this->path[$s]=0;
$this->dist[$s]=0;
$que->InQ($s);
$this->vst[$s]=1;
while($que->QIsFull()!=0)
{
$from=$que->getFrontDate();
//$que.pop();
//array_shift($que);
$que->OutQ();
$vst[$from]=0;
$cot[$from]++;
if($this->cot[$from]>=$this->N)
return 0;
for($i=$this->head[$from];$i+1;$i=$this->edge[i]->next)
// head=-1 , ,
{
$to=$this->edge[$i].to;
if($this->dist[$to]>$this->dist[$from]+$this->edge[$i]->w)
{
$this->dist[$to] = $this->dist[$from] + $this->edge[$i]->w;
if(!$this->vst[$to])
$this->$que->InQ($to);
$this->vst[$to]=1;
}
}
}
for($i=1;$i<=$N;$i++)
echo "dist".$this->i." = ".$this->dist[i]."<br>";
return 1;
}
function init()
{
$from;
$to;
$w;
$this->size=0;
//memset(head,-1,sizeof(head));
for($i=0;$i<count($this->head);$i++)
$this->head[i] = -1;
}
function main()
{
$this->init();
$this->M = 3;
$this->N = 3;
$from = 1;
$w = 3 ;
$to = 2;
$this->InsertEdge($from,$to,$w);
$from = 2;
$w = 1 ;
$to = 3;
$this->InsertEdge($from,$to,$w);
$from = 3;
$w = 3 ;
$to = 2;
$this->InsertEdge($from,$to,$w);
if(!$this->spfa(1))
echo " ";
else echo " ";
return 0;
}
}
class queue{
protected $front;//
protected $rear;//
protected $queue=array('0'=>' ');//
protected $maxsize;//
public function __construct($size){
$this->initQ($size);
}
//
private function initQ($size){
$this->front=0;
$this->rear=0;
$this->maxsize=$size;
}
//
public function QIsEmpty(){
return $this->front==$this->rear;
}
//
public function QIsFull(){
return ($this->front-$this->rear)==$this->maxsize;
}
//
public function getFrontDate(){
return $this->queue[$this->front]->getData();
}
//
public function InQ($data){
if($this->QIsFull())echo $data.": !( , !)<br>";
else {
$this->front++;
for($i=$this->front;$i>$this->rear;$i--){
//echo $data;
if($this->queue[$i])unset($this->queue[$i]);
$this->queue[$i]=$this->queue[$i-1];
}
$this->queue[$this->rear+1]=new data($data);
}
}
//
public function OutQ(){
if($this->QIsEmpty())echo " !<br>";
else{
unset($this->queue[$this->front]);
$this->front--;
}
}
}
class data {
//
private $data;
public function __construct($data){
$this->data=$data;
}
public function getData(){
return $this->data;
}
public function __destruct(){
}
}
?>
<?php
$a = new A();
$a->main();
?>